This paper provides an analysis of a natural d-round tournament over n = 2d 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\\cdotn$, $c7.44$, that sorts the vast majority of the n! possible input permutations; an $O(n)$-depth hypercubic comparator network that sorts the vast majority of permutations; a hypercubic sorting network with nearly logarithmic depth; an $O(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 $(nn)$-node omega machine in $O(m+n)$ bit steps.
%0 Journal Article
%1 leighton98
%A Leighton, Tom
%A Plaxton, C. Greg
%D 1998
%I SIAM
%J SIAM Journal on Computing
%K algorithm graph.theory sorting sorting.network
%N 1
%P 1--47
%R 10.1137/s0097539794268406
%T Hypercubic Sorting Networks
%V 27
%X This paper provides an analysis of a natural d-round tournament over n = 2d 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\\cdotn$, $c7.44$, that sorts the vast majority of the n! possible input permutations; an $O(n)$-depth hypercubic comparator network that sorts the vast majority of permutations; a hypercubic sorting network with nearly logarithmic depth; an $O(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 $(nn)$-node omega machine in $O(m+n)$ bit steps.
@article{leighton98,
abstract = {This paper provides an analysis of a natural d-round tournament over n = 2d 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.},
added-at = {2016-11-07T00:51:47.000+0100},
author = {Leighton, Tom and Plaxton, C. Greg},
biburl = {https://www.bibsonomy.org/bibtex/2ddb5dc3abf0b4a2bc482fdbbcfb45834/ytyoun},
doi = {10.1137/s0097539794268406},
interhash = {c896913bab5c654ba588c29d4a4dc776},
intrahash = {ddb5dc3abf0b4a2bc482fdbbcfb45834},
journal = {{SIAM} Journal on Computing},
keywords = {algorithm graph.theory sorting sorting.network},
month = feb,
number = 1,
pages = {1--47},
publisher = {SIAM},
timestamp = {2016-11-08T08:58:54.000+0100},
title = {Hypercubic Sorting Networks},
volume = 27,
year = 1998
}