1983 · 38 citations · 7 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer NetworksInterconnection NetworksParallel SortingShuffle-exchange NetworksSorting AlgorithmsSorting ProblemsParallel Sorting NetworksShuffle-exchange TopologySortingSorting Networks
This paper introduces a new sorting network, called the balanced sorting network, that sorts n items in O([lgn]2) time using (n/2)(lgn)2 comparators. Although these bounds are comparable to many existing sorting networks, the balanced sorting network possess some distinct advantages. In particular, its structure is highly regular consisting of a sequence of identicalbalanced 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.
7
Sorting networks and their applications
Kenneth E. Batcher · 1968 · 2.4K citations
Parallel Processing with the Perfect Shuffle
Harold S. Stone · IEEE Transactions on Computers · 1971 · 1.3K citations
Miklós Ajtai, János Komlós, Endre Szemerédi · 1983 · 671 citations
A high-speed sorting procedure
Donald L. Shell · Communications of the ACM · 1959 · 197 citations · Full text
Larry Rudolph · IEEE Transactions on Computers · 1985 · 59 citations