An 0(n log n) sorting network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An 0(n log n) sorting network

Full text

Pdf (553 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the fifteenth annual ACM symposium on Theory of computing table of contents

Pages: 1 - 9

Year of Publication: 1983

ISBN:0-89791-099-0

Authors

M. Ajtai
J. Komlós
E. Szemerédi

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 174, Citation Count: 91

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800061.808726 What is a DOI?

ABSTRACT

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n). A natural way of sorting is through consecutive halvings: determine the upper and lower halves of the set, proceed similarly within the halves, and so on. Unfortunately, while one can halve a set using only 0(n) comparisons, this cannot be done in less than log n (parallel) time, and it is known that a halving network needs (½)n log n comparisons. It is possible, however, to construct a network of 0(n) comparisons which halves in constant time with high accuracy. This procedure (&egr;-halving) and a derived procedure (&egr;-nearsort) are described below, and our sorting network will be centered around these elementary steps.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Angluin, A note on a construction of Margulis, Information Processing Letters 8(1), 1979, 17-19.
	2	K. Batcher, Sorting networks and their applications, AFIPS Spring Joint Computer Conference 32(1968), 307-314.
	3	O. Gabber and Z. Galil, Explicit constructions of linear size superconcentrators, Proc. 20th Ann. Symp. Found. Comp. Sci., 1979, 364-370.
	4	M. Klawe, Non-existence of one-dimensional expanding graphs, IEEE, 1981, 109-114.
	5	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	6	G. Margulis, Explicit constructions of concentrators, Problemy Peredachi Informatsii 9(4), 1973, 71-80 (English translation in Problems of Information Transmission, Plenum, N.Y., 1975.
	7	W. Paul, R. Tarjan and J. Celoni, Space bounds for a game on graphs, Mathematical Systems Theory 10, 1979, 239-251.
	8	M. Pinsker, On the complexity of a concentrator, 7th International Teletraffic Conference, Stockholm, June 1973, 318/1-318/4.
	9	N. Pippenger, Superconcentrators, SIAM J. Computing 6(2), 1977, 298-304.
	10	Leslie G. Valiant, On non-linear lower bounds in computational complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.45-53, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803752]

CITED BY 91

	Hussein M. Alnuweiri, Optimal bounded-degree VLSI networks for sorting in a constant number of rounds, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.732-739, November 18-22, 1991, Albuquerque, New Mexico, United States
	Richard Cole , Micha Sharir , Chee K. Yap, On k-hulls and related problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.154-166, December 1984
	Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.427-436, May 29-June 01, 1995, Las Vegas, Nevada, United States
	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States
	M Ajtai , J Komlos , W L Steiger , E Szemeredi, Deterministic selection in O(loglog N) parallel time, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.188-195, May 28-30, 1986, Berkeley, California, United States
	G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989
	Adnan Agbaria , Yosi Ben-Asher , Ilan Newman, Communication-processor tradeoffs in limited resources PRAM, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.74-82, June 27-30, 1999, Saint Malo, France
	Noam Nisan , Amnon Ta-Shma, Symmetric logspace is closed under complement, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.140-146, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Mihir Bellare , Oded Goldreich , Shafi Goldwasser, Incremental cryptography and application to virus protection, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.45-56, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996
	Michael Molloy , Bruce Reed, Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.524-529, May 24-26, 1998, Dallas, Texas, United States
	O. Goldreich, Towards a theory of software protection and simulation by oblivious RAMs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.182-194, January 1987, New York, New York, United States
	D. E. Willard , Y. C. Wee, Quasi-Valid range querying and its implications for nearest neighbor problems, Proceedings of the fourth annual symposium on Computational geometry, p.34-43, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	D. Peleg , E. Upfal, Constructing disjoint paths on expander graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.264-273, January 1987, New York, New York, United States
	N. Nishimura, Asynchronous shared memory parallel computation, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.76-84, July 02-06, 1990, Island of Crete, Greece
	Malika De , Debasish Das , Mabhin Ghosh , Bhabani P. Sinha, An Efficient Sorting Algorithm on the Multi-Mesh Network, IEEE Transactions on Computers, v.46 n.10, p.1132-1137, October 1997
	Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States
	Chris Armen, Bounds on the separation of two parallel disk models, Proceedings of the fourth workshop on I/O in parallel and distributed systems: part of the federated computing research conference, p.122-127, May 27-27, 1996, Philadelphia, Pennsylvania, United States
	A. A. Razborov, On the method of approximations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.167-176, May 14-17, 1989, Seattle, Washington, United States
	Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984
	Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.463-472, September 1992, Orlando, Florida, United States
	B Bollobás , I Simon, On the expected behavior of disjoint set union algorithms, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.224-231, May 06-08, 1985, Providence, Rhode Island, United States
	Robert Beals , Tetsuro Nishino , Keisuke Tanaka, More on the complexity of negation-limited circuits, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.585-595, May 29-June 01, 1995, Las Vegas, Nevada, United States
	K. Herley, Space-efficient representations of shared data for parallel computers, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.407-416, July 02-06, 1990, Island of Crete, Greece
	Yu Lin-Kriz , Victor Pan, On parallel complexity of integer linear programming, GCD and the iterated mod function, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.124-137, September 1992, Orlando, Florida, United States
	J. Matoušek, Construction of epsilon nets, Proceedings of the fifth annual symposium on Computational geometry, p.1-10, June 05-07, 1989, Saarbruchen, West Germany
	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987
	Mark H. Nodine , Jeffrey Scott Vitter, Greed sort: optimal deterministic sorting on parallel disks, Journal of the ACM (JACM), v.42 n.4, p.919-933, July 1995
	Guy E. Blelloch , Margaret Reid-Miller, Pipelining with futures, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.249-259, June 23-25, 1997, Newport, Rhode Island, United States
	Martin Dowd , Yehoshua Perl , Larry Rudolph , Michael Saks, The periodic balanced sorting network, Journal of the ACM (JACM), v.36 n.4, p.738-757, Oct. 1989
	Nicholas Pippenger, Self-routing superconcentrators, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.355-361, May 16-18, 1993, San Diego, California, United States
	Hussein M. Alnuweiri , V. K. Prasanna Kumar, Optimal VLSI Sorting with Reduced Number of Processors, IEEE Transactions on Computers, v.40 n.1, p.105-110, January 1991
	Sanguthevar Rajasekaran, A framework for simple sorting algorithms on parallel disk systems (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.88-97, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Q. P. Gu , J. Gu, Algorithms and Average Time Bounds of Sorting on a Mesh-Connected Computer, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.308-315, March 1994
	Marek Chrobak , David Eppstein , Giuseppe F. Italiano , Moti Yung, Efficient sequential and parallel algorithms for computing recovery points in trees and paths, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.158-167, January 28-30, 1991, San Francisco, California, United States
	Nir Shavit , Eli Upfal , Asaph Zemach, A wait-free sorting algorithm, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.121-128, August 21-24, 1997, Santa Barbara, California, United States
	Ernst W. Mayr , Ralph Werchner, Optimal routing of parentheses on the hypercube, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.109-117, June 29-July 01, 1992, San Diego, California, United States
	Ilan Bar-on , Uzi Vishkin, Optimal parallel generation of a computation tree form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.348-357, April 1985
	Keisuke Tanaka , Tetsuro Nishino, On the complexity of negation-limited Boolean networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.38-47, May 23-25, 1994, Montreal, Quebec, Canada
	Biing-Feng Wang , Shan-Chyun Ku , Keng-Hua Shil, Cost-Optimal Parallel Algorithms for the Tree Bisector and Related Problems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.888-898, September 2001
	Thomas M. Stricker, Supporting the hypercube programming model on mesh architectures: (a fast sorter for iWarp tori), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.148-157, June 29-July 01, 1992, San Diego, California, United States
	Torben Hagerup , T. Radzik, Every robust CRCW PRAM can efficiently simulate a PRIORITY PRAM, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.117-124, July 02-06, 1990, Island of Crete, Greece
	Eli Upfal, An O(log N) deterministic packet-routing scheme, Journal of the ACM (JACM), v.39 n.1, p.55-70, Jan. 1992
	Marek Piotrów, Depth optimal sorting networks resistant to k passive faults, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.242-251, January 28-30, 1996, Atlanta, Georgia, United States
	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks and multi-processor coordination, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.348-358, May 05-08, 1991, New Orleans, Louisiana, United States
	Yukon Chang , Janos Simon, Continuous routing and batch routing on the hypercube, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.272-281, August 11-13, 1986, Calgary, Alberta, Canada
	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994
	I. Parberry, A computer assisted optimal depth lower bound for sorting networks with nine inputs, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.152-161, November 12-17, 1989, Reno, Nevada, United States
	Marek Piotrów, Periodic, random-fault-tolerant correction networks, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.298-305, July 2001, Crete Island, Greece
	C P Schnorr , A Shamir, An optimal sorting algorithm for mesh connected computers, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.255-263, May 28-30, 1986, Berkeley, California, United States
	Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987
	L. Fava Lindon , S. G. Akl, An Optimal Implementation of Broadcasting with Selective Reduction, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.256-269, March 1993
	Giovanni di Crescenzo , Yair Frankel, Existence of multiplicative secret sharing schemes with polynomial share expansion, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.895-896, January 17-19, 1999, Baltimore, Maryland, United States
	S. Muthukrishnan , Mike Paterson , Süleyman Cenk Sahinalp , Torsten Suel, Compact grid layouts of multi-level networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.455-463, May 01-04, 1999, Atlanta, Georgia, United States
	M. Dowd , Y. Perl , M. Saks , L. Rudolph, The balanced sorting network, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.161-172, August 17-19, 1983, Montreal, Quebec, Canada
	Torben Hagerup, Optimal parallel string algorithms: sorting, merging and computing the minimum, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.382-391, May 23-25, 1994, Montreal, Quebec, Canada
	B. G. Douglass, Rearrangeable Three-Stage Interconnection Networks and Their Routing Properties, IEEE Transactions on Computers, v.42 n.5, p.559-567, May 1993
	Marek Piotrów, A note on constructing binary heaps with periodic networks, Information Processing Letters, v.83 n.3, p.129-134, 16 August 2002
	Yujie Han , Robert A. Wagner, An efficient and fast parallel-connected component algorithm, Journal of the ACM (JACM), v.37 n.3, p.626-642, July 1990
	Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992
	S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States
	Tom Leighton , Yuan Ma , Torsten Suel, On probabilistic networks for selection, merging, and sorting, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.106-118, June 24-26, 1995, Santa Barbara, California, United States
	Zhaofang Wen, Multiway Merging in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.11-17, January 1996
	Xiaojun Guan , Michael A. Langston, Time-Space Optimal Parallel Merging and Sorting, IEEE Transactions on Computers, v.40 n.5, p.596-602, May 1991
	Ted H. Szymanski, Design Principles for Practical Self-Routing Nonblocking Switching Networks with O(N · log N) Bit-Complexity, IEEE Transactions on Computers, v.46 n.10, p.1057-1069, October 1997
	Jae-Dong Lee , Kenneth E. Batcher, Minimizing Communication in the Bitonic Sort, IEEE Transactions on Parallel and Distributed Systems, v.11 n.5, p.459-474, May 2000
	P. J. Bernhard , D. J. Rosenkrantz, Partitioning Message Patterns for Bundled Omega Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.353-363, April 1994
	Hagit Attiya , Maurice Herlihy , Ophir Rachman, Atomic snapshots using lattice agreement, Distributed Computing, v.8 n.3, p.121-132, March 1995
	Eran Aharonson , Hagit Attiya, Counting networks with arbitrary fan-out, Distributed Computing, v.8 n.4, p.163-169, June 1995
	Ching Yuh Jan , A. Yavuz Oruç, Fast Self-Routing Permutation Switching on an Asymptotically Minimum Cost Network, IEEE Transactions on Computers, v.42 n.12, p.1469-1479, December 1993
	Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	M. R. Samatham , D. K. Pradhan, The de Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, IEEE Transactions on Computers, v.38 n.4, p.567-581, April 1989
	Toshiyuki Fujiwara , Kazuo Iwama , Chuzo Iwamoto, Partially effective randomization in simulations between arbitrary and common PRAMs, Journal of Parallel and Distributed Computing, v.64 n.3, p.319-326, March 2004
	I. D. Scherson , S. Sen, Parallel Sorting in Two-Dimensional VLSI Models of Computation, IEEE Transactions on Computers, v.38 n.2, p.238-249, February 1989
	Amos Beimel , Enav Weinreb, Monotone circuits for monotone weighted threshold functions, Information Processing Letters, v.97 n.1, p.12-18, 16 January 2006
	Vijaya Ramachandran , Brian Grayson , Michael Dahlin, Emulations between QSM, BSP and LogP: a framework for general-purpose parallel algorithm design, Journal of Parallel and Distributed Computing, v.63 n.12, p.1175-1192, December 2003
	G. Bilardi , F. P. Preparata, A minimum area VLSI network for O(logn) time sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.64-70, December 1984
	Bradley C. Kuszmaul, Fast, Deterministic Routing, on Hypercubes, Using Small Buffers, IEEE Transactions on Computers, v.39 n.11, p.1390-1393, November 1990
	Tom Leighton, Tight bounds on the complexity of parallel sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.71-80, December 1984
	Naomi Nishimura, Asynchronous shared memory parallel computation (preliminary version), ACM SIGARCH Computer Architecture News, v.19 n.1, p.97-105, March 1991
	Jesper Jansson , Wing-Kin Sung, Inferring a level-1 phylogenetic network from a dense set of rooted triplets, Theoretical Computer Science, v.363 n.1, p.60-68, 25 October 2006
	M. R. Samatham , D. K. Pradhan, The de Bruijn multiprocessor network: a versatile sorting network, ACM SIGARCH Computer Architecture News, v.13 n.3, p.360-367, June 1985
	R. Ostrovsky, Efficient computation on oblivious RAMs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.514-523, May 13-17, 1990, Baltimore, Maryland, United States
	R. Cypher, A lower bound on the size of shellsort networks, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.58-63, June 18-21, 1989, Santa Fe, New Mexico, United States
	A. Aggarwal , A. K. Chandra , M. Snir, On communication latency in PRAM computations, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.11-21, June 18-21, 1989, Santa Fe, New Mexico, United States
	Rodica Ceterchi , Alexandru Ioan Tomescu, Implementing Sorting Networks with Spiking Neural P Systems, Fundamenta Informaticae, v.87 n.1, p.35-48, November 2008
	Franco P. Preparata, The unpredictable deviousness of models, Theoretical Computer Science, v.408 n.2-3, p.99-105, November, 2008
	Kazuo Iwama , Hiroki Morizumi , Jun Tarui, Reductions for monotone Boolean circuits, Theoretical Computer Science, v.408 n.2-3, p.208-212, November, 2008
	Hiroki Morizumi , Jun Tarui, Linear-size log-depth negation-limited inverter for k-tonic binary sequences, Theoretical Computer Science, v.410 n.11, p.1054-1060, March, 2009
	Kunsoo Park , Heejin Park , Woo-Chul Jeun , Soonhoi Ha, Boolean circuit programming: A new paradigm to design parallel algorithms, Journal of Discrete Algorithms, v.7 n.2, p.267-277, June, 2009
	Hongtu Jiang , Hakän Ardö , Viktor Öwall, A hardware architecture for real-time video segmentation utilizing memory reduction techniques, IEEE Transactions on Circuits and Systems for Video Technology, v.19 n.2, p.226-236, February 2009