A (fairly) simple circuit that (usually) sorts
- 4 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 264-274
- https://doi.org/10.1109/fscs.1990.89545
Abstract
A natural k-round tournament over n=2/sup k/ players is analyzed, and it is demonstrated that the tournament possesses a surprisingly strong ranking property. The ranking property of this tournament is exploited by being used as a building block for efficient parallel sorting algorithms under a variety of different models of computation. Three important applications are provided. First, a sorting circuit of depth 7.44 log n, which sorts all but a superpolynomially small fraction of the n-factorial possible input permutations, is defined. Secondly, a randomized sorting algorithm that runs in O(log n) word steps with very high probability is given for the hypercube and related parallel computers (the butterfly, cube-connected cycles, and shuffle-exchange). Thirdly, a randomized algorithm that runs in O(m+log n)-bit steps with very high probability is given for sorting n O(m)-bit records on an n log n-node butterfly.Keywords
This publication has 7 references indexed in Scilit:
- Improved sorting networks withO(logN) depthAlgorithmica, 1990
- Fast algorithms for bit-serial routing on a hypercubePublished by Association for Computing Machinery (ACM) ,1990
- A logarithmic time sort for linear size networksJournal of the ACM, 1987
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Sorting inc logn parallel stepsCombinatorica, 1983
- Optimal Rearrangeable Multistage Connecting NetworksBell System Technical Journal, 1964
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952