Article

Free access

An 0(n log n) sorting network

Authors:

M. Ajtai,

J. Komlós,

E. SzemerédiAuthors Info & Claims

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

Pages 1 - 9

https://doi.org/10.1145/800061.808726

Published: 01 December 1983 Publication History

PDF eReader

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 (ε-halving) and a derived procedure (ε-nearsort) are described below, and our sorting network will be centered around these elementary steps.

References

[1]

D. Angluin, A note on a construction of Margulis, Information Processing Letters 8(1), 1979, 17-19.

Crossref

Google Scholar

[2]

K. Batcher, Sorting networks and their applications, AFIPS Spring Joint Computer Conference 32(1968), 307-314.

Google Scholar

[3]

O. Gabber and Z. Galil, Explicit constructions of linear size superconcentrators, Proc. 20th Ann. Symp. Found. Comp. Sci., 1979, 364-370.

Digital Library

Google Scholar

[4]

M. Klawe, Non-existence of one-dimensional expanding graphs, IEEE, 1981, 109-114.

Digital Library

Google Scholar

[5]

D.E. Knuth, The Art of Computer Programming, Addison-Wesley, Vol. 3, pp. 220-246 (and Exercises 49 and 51).

Digital Library

Google Scholar

[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.

Google Scholar

[7]

W. Paul, R. Tarjan and J. Celoni, Space bounds for a game on graphs, Mathematical Systems Theory 10, 1979, 239-251.

Crossref

Google Scholar

[8]

M. Pinsker, On the complexity of a concentrator, 7th International Teletraffic Conference, Stockholm, June 1973, 318/1-318/4.

Google Scholar

[9]

N. Pippenger, Superconcentrators, SIAM J. Computing 6(2), 1977, 298-304.

Digital Library

Google Scholar

[10]

L.G. Valiant, On nonlinear lower bounds in computational complexity, Proc. 7th Annual ACM Symp. on Theory of Computing, Albuquerque, N.M., May 1975, 45-53.

Digital Library

Google Scholar

Cited By

View all

Wang JWang KLin XZhang WZhang Y(2024)Efficient Unsupervised Community Search with Pre-Trained Graph TransformerProceedings of the VLDB Endowment10.14778/3665844.366585317:9(2227-2240)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665853
Fisch BLazzaretti ALiu ZPapamanthou CLuo BLiao XXu JKirda ELie D(2024)ThorPIR: Single Server PIR via Homomorphic Thorp ShufflesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690326(1448-1462)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690326
Jin CYin Cvan Dijk MDuan SMassacci FReiter MZhang HLuo BLiao XXu JKirda ELie D(2024)PG: Byzantine Fault-Tolerant and Privacy-Preserving Sensor Fusion with Guaranteed Output DeliveryProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670343(3272-3286)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670343
Show More Cited By

Index Terms

An 0(n log n) sorting network
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space
FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer Science

We present a randomized algorithm sorting n integers in 0(n\sqrt {\log \log n}) expected time and linear space. This improves the previous O(n log log n) bound by Anderson et al. from STOC'95. As an immediate consequence, if the integers are bounded by ...
Sorting in Linear Time?

We show that a unit-cost RAM with a word length ofwbits can sortnintegers in the range 0 2w 1 inO(nloglogn) time for arbitraryw logn, a significant improvement over the bound ofO(nlogn) achieved by the fusion trees of Fredman and Willard. Provided thatw ...
A hypercubic sorting network with nearly logarithmic depth
STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

A natural class of “hypercubic” sorting networks is defined. The regular structure of these sorting networks allows for elegant and efficient implementations on any of the so-called hypercubic networks (e.g., the hypercube, shuffle-exchange, butterfly, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

December 1983

487 pages

ISBN:0897910990

DOI:10.1145/800061

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

379
Total Citations
View Citations
2,230
Total Downloads

Downloads (Last 12 months)781
Downloads (Last 6 weeks)83

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang JWang KLin XZhang WZhang Y(2024)Efficient Unsupervised Community Search with Pre-Trained Graph TransformerProceedings of the VLDB Endowment10.14778/3665844.366585317:9(2227-2240)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665853
Fisch BLazzaretti ALiu ZPapamanthou CLuo BLiao XXu JKirda ELie D(2024)ThorPIR: Single Server PIR via Homomorphic Thorp ShufflesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690326(1448-1462)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690326
Jin CYin Cvan Dijk MDuan SMassacci FReiter MZhang HLuo BLiao XXu JKirda ELie D(2024)PG: Byzantine Fault-Tolerant and Privacy-Preserving Sensor Fusion with Guaranteed Output DeliveryProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670343(3272-3286)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670343
Haeupler BPatel SRoeyskoe AStein CZuzic GMohar BShinkar IO'Donnell R(2024)Polylog-Competitive Deterministic Local Routing and SchedulingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649678(812-822)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649678
Chang ZXie DWang SLi FShen Y(2024)Towards Practical Oblivious Join ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.331003836:4(1829-1842)Online publication date: Apr-2024
https://doi.org/10.1109/TKDE.2023.3310038
Xie HYan Z(2024)SPCEX: Secure and Privacy-preserving Cryptocurrency ExchangeIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.3353541(1-14)Online publication date: 2024
https://doi.org/10.1109/TDSC.2024.3353541
Ngai NDemertzis IChamani JPapadopoulos D(2024)Distributed & Scalable Oblivious Sorting and Shuffling2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00153(4277-4295)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00153
Donev V(2024)An Algorithm for Sorting an Array with Non-Repeating Numbers by Direct Positioning2024 59th International Scientific Conference on Information, Communication and Energy Systems and Technologies (ICEST)10.1109/ICEST62335.2024.10639780(1-4)Online publication date: 1-Jul-2024
https://doi.org/10.1109/ICEST62335.2024.10639780
Radha NRaghavan RKarthika SSwathika R(2024)RetrORAM: Oblivious Random Access Machines in Retrospect2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT61001.2024.10724915(1-9)Online publication date: 24-Jun-2024
https://doi.org/10.1109/ICCCNT61001.2024.10724915
Segovia-Aguas JJiménez SJonsson A(2024)Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objectsArtificial Intelligence10.1016/j.artint.2024.104097(104097)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104097
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space

Sorting in Linear Time?

A hypercubic sorting network with nearly logarithmic depth

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations