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 language||English (US)|
|Title of host publication||Unknown Host Publication Title|
|Number of pages||12|
|ISBN (Print)||0897911105, 9780897911108|
|State||Published - 1983|
All Science Journal Classification (ASJC) codes