%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 }