Hypercubic Sorting Networks
Tom Leighton, C. Greg Plaxton · SIAM Journal on Computing · 1998
This paper provides an analysis of a natural d-round tournament over n = 2 d players and demonstrates that the tournament possesses a surprisingly strong ranking property. The ranking property of this tournament is used to design efficient sorting algorithms for several models of parallel computation: a comparator network of depth $c\\cdot\lg n$, $c\approx 7.44$, that sorts the vast majority of the n! possible input permutations; an $O(\lg n)$-depth hypercubic comparator network that sorts the vast majority of permutations; a hypercubic sorting network with nearly logarithmic depth; an $O(\lg n)$-time randomized sorting algorithm for any hypercubic machine (other such algorithms have been previously discovered, but this algorithm has a significantly smaller failure probability than any previously known algorithm); and a randomized algorithm for sorting nO (m)-bit records on an $(n\lg n)$-node omega machine in $O(m+\lg n)$ bit steps.
Cited by 34 works. doi:10.1137/s0097539794268406
Authors
References
- The Art of Computer Programming
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Sorting networks and their applications
- The Art of Computer Programming, Vol. 2
- Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
- Universal Schemes for Parallel Communication
- On the Distribution of the Number of Successes in Independent Trials
- Sorting inc logn parallel steps
- Optimal Rearrangeable Multistage Connecting Networks
- A logarithmic time sort for linear size networks