BALANCED SORTING NETWORK.

M. Dowd, Y. Perl, M. Saks, L. Rudolph

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

This paper introduces a new sorting network, called the balanced sorting network, that sorts n items in OMICRON ( left bracket lg n right bracket **2) time using (n/2)(lg n)**2 comparators. Although these bounds are comparable to many existing sorting networks, the balanced sorting network possesses some distinct advantages. In particular, its structure is highly regular consisting of a sequence of identical balanced merging networks. We prove that lg n identical merging networks are both necessary and sufficient to sort n items. We also present an explicit implementation of our network on the shuffle exchange interconnection model in which the direction of the comparitors are all identical and fixed.

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherACM
Pages161-172
Number of pages12
ISBN (Print)0897911105, 9780897911108
DOIs
StatePublished - 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'BALANCED SORTING NETWORK.'. Together they form a unique fingerprint.

Cite this