{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:25Z","timestamp":1787337505853,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    This paper provides an analysis of a natural d-round tournament over n = 2\n                    <jats:sup>d<\/jats:sup>\n                    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.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794268406","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1-47","source":"Crossref","is-referenced-by-count":16,"title":["Hypercubic Sorting Networks"],"prefix":"10.1137","volume":"27","author":[{"given":"Tom","family":"Leighton","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. Greg","family":"Plaxton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090402"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di,\n                      Halvers and expanders\n                      , in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 686\u2013692.","DOI":"10.1109\/SFCS.1992.267782"},{"key":"R4","first-page":"307","volume":"32","author":"Batcher K. E.","year":"1968","journal-title":"Proceedings of the AFIPS Spring Joint Computer Conference"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1964.tb04103.x"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0222027"},{"key":"R8","unstructured":"R. E. Cypher and C. G. Plaxton,\n                      Techniques for Shared Key Sorting\n                      , Tech. Report RJ 7347, Computer Science Department, IBM Almaden Research Center, San Jose, CA, 1990."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Robert Cypher, C. Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), Vol. 47, 1993, 501\u201354894m:68029","DOI":"10.1016\/0022-0000(93)90043-V"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728178"},{"key":"R11","volume-title":"The art of computer programming. Vol. 2","author":"Knuth Donald","year":"1981"},{"key":"R12","volume-title":"Introduction to parallel algorithms and architectures","author":"Leighton F.","year":"1992"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1030"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Tom Leighton, C. Plaxton, A (fairly) simple circuit that (usually) sorts, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 264\u201327492j:68018","DOI":"10.1109\/FSCS.1990.89545"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840378"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"C. G. Plaxton,\n                      A hypercubic sorting network with nearly logarithmic depth\n                      , in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 405\u2013416.","DOI":"10.1145\/129712.129751"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01184936"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90005-P"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7532"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"L. G. Valiant and G. J. Brebner,\n                      Universal schemes for parallel communication\n                      , in Proceedings of the 13th Annual ACM Symposium on Theory of Computing, ACM, New York, 1981, pp. 263\u2013277.","DOI":"10.1145\/800076.802479"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794268406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:25Z","timestamp":1787336065000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794268406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794268406"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794268406","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}