Article

Deterministic sorting in O(nlog log n) time and linear space

Author:

Yijie HanAuthors Info & Claims

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

Pages 602 - 608

https://doi.org/10.1145/509907.509993

Published: 19 May 2002 Publication History

Abstract

We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2, …, m—1} in linear space in O(n log log n) time. This improves our previous result [8] which sorts in O(n log log n log log log n) time and linear space. This also improves previous best deterministic sorting algorithm [3, 11] which sorts in O(nlog log n) time but uses O(m^ε) space. Our results can also be compared with Thorup's previous result [16] which sorts in O(nlog log n) time and linear space but uses randomization.

References

[1]

S. Albers and T. Hagerup. Improved parallel integer sorting without concurrent writing. Information and Computation, 136, 25--51(1997).]]

Digital Library

[2]

A. Andersson. Fast deterministic sorting and searching in linear space. Proc. 1996 IEEE Symp. on Foundations of Computer Science, 135--141(1996).]]

Digital Library

[3]

A. Andersson, T. Hagerup, S. Nilsson, R. Raman. Sorting in linear time? Proc. 1995 Symposium on Theory of Computing, 427--436(1995).]]

Digital Library

[4]

P. van Emde Boas, R. Kaas, E. Zijlstra. Design and implementation of an efficient priority queue. (MATH). Syst. Theory 10 99--127(1977).]]

[5]

M. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen. A reliable randomized algorithm for the closest-pair problem. J. Algorithms 25, 19--51(1997).]]

Digital Library

[6]

M.L. Fredman, D.E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. System Sci. 47, 424--436(1994).]]

Digital Library

[7]

T. Hagerup and H. Shen. Improved nonconservative sequential and parallel integer sorting. Infom. Process. Lett. 36, pp. 57--63(1990).]]

Digital Library

[8]

Y. Han. Improved fast integer sorting in linear space. Information and Computation}-, Vol. 170, No. 1, 81--94(Oct. 2001).]]

Digital Library

[9]

Y. Han, Fast integer sorting in linear space. Symp. Theoretical Aspects of Computing (STACS'2000), Lecture Notes in Computer Science 1170, 242--253(Feb. 2000).]]

Digital Library

[10]

Y. Han, M. Thorup. Sorting integers in O(n√ \over loglog n) expected time and linear space. Manuscript.]]

[11]

Y. Han, X. Shen. Conservative algorithms for parallel and sequential integer sorting. Proc. 1995 International Computing and Combinatorics Conference, Lecture Notes in Computer Science 959, 324--333(August, 1995).]]

Digital Library

[12]

D. Kirkpatrick and S. Reisch. Upper bounds for sorting integers on random access machines. Theoretical Computer Science 28, 263--276(1984).]]

[13]

F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publ., San Mateo, CA. 1992.]]

Digital Library

[14]

R. Raman. Priority queues: small, monotone and trans-dichotomous. Proc. 1996 European Symp. on Algorithms, Lecture Notes in Computer Science 1136, 121--137(1996).]]

Digital Library

[15]

M. Thorup. Fast deterministic sorting and priority queues in linear space. Proc. 1998 ACM-SIAM Symp. on Discrete Algorithms (SODA'98), 550--555(1998).]]

Digital Library

[16]

M. Thorup. Randomized sorting in O(n log log n)time and linear space using addition, shift, and bit-wise boolean operations. Proc. 8th ACM-SIAM Symp. on Discrete Algorithms (SODA'97), 352--359(1997).]]

Digital Library

Cited By

Jafargholi ZLarsen KSimkin MMarx D(2021)Optimal oblivious priority queuesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458205(2366-2383)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458205
Farhadi AHajiaghayi MLarsen KShi E(2021)Lower Bounds for External Memory Integer Sorting via Network CodingSIAM Journal on Computing10.1137/20M132188752:2(STOC19-87-STOC19-111)Online publication date: 30-Sep-2021
https://doi.org/10.1137/20M1321887
Farhadi AHajiaghayi MLarsen KShi E(2020)Lower bounds for external memory integer sorting via network codingCommunications of the ACM10.1145/341626863:10(97-105)Online publication date: 23-Sep-2020
https://dl.acm.org/doi/10.1145/3416268
Show More Cited By

Index Terms

Deterministic sorting in O(nlog log n) time and linear space
1. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching
  2. Randomness, geometry and discrete structures

Recommendations

Equivalence between priority queues and sorting

We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to n keys in S(n) time per key, then there is a priority queue supporting delete and insert in O(S(n)) time and find-min in ...
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 ...
Deterministic sorting in O(nlog logn) time and linear space

We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0,1,2, ..., m - 1} in linear space in O(n log log n) time. This improves our previous result [Y. Han, Inform. and Comput. 170 (1) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

May 2002

840 pages

ISBN:1581134959

DOI:10.1145/509907

Conference Chair:
John Reif
Duke University

Copyright © 2002 ACM.

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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC02

Sponsor:

SIGACT

STOC02: Symposium on the Theory of Computing

May 19 - 21, 2002

Quebec, Montreal, Canada

Acceptance Rates

STOC '02 Paper Acceptance Rate 91 of 287 submissions, 32%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
220
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)3

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jafargholi ZLarsen KSimkin MMarx D(2021)Optimal oblivious priority queuesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458205(2366-2383)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458205
Farhadi AHajiaghayi MLarsen KShi E(2021)Lower Bounds for External Memory Integer Sorting via Network CodingSIAM Journal on Computing10.1137/20M132188752:2(STOC19-87-STOC19-111)Online publication date: 30-Sep-2021
https://doi.org/10.1137/20M1321887
Farhadi AHajiaghayi MLarsen KShi E(2020)Lower bounds for external memory integer sorting via network codingCommunications of the ACM10.1145/341626863:10(97-105)Online publication date: 23-Sep-2020
https://dl.acm.org/doi/10.1145/3416268
Jiang SLarsen KChan T(2019)A faster external memory priority queue with DecreaseKeysProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310516(1331-1343)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310516
Basat REinziger GGong JMoraney JRaz D(2019)q-MAXProceedings of the Internet Measurement Conference10.1145/3355369.3355569(322-336)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3355369.3355569
Farhadi AHajiaghayi MLarsen KShi ECharikar MCohen E(2019)Lower bounds for external memory integer sorting via network codingProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316337(997-1008)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316337
Wang SLv T(2019)Deep Reinforcement Learning Based Dynamic Multichannel Access in HetNets2019 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2019.8885857(1-6)Online publication date: 15-Apr-2019
https://dl.acm.org/doi/10.1109/WCNC.2019.8885857
Dinh ABao NKhalid MIida H(2019)Simulating competitiveness and precision in a tournament structure: a reaper tournament systemInternational Journal of Information Technology10.1007/s41870-019-00397-5Online publication date: 18-Nov-2019
https://doi.org/10.1007/s41870-019-00397-5
Duan RPettie SSu H(2018)Scaling Algorithms for Weighted Matching in General GraphsACM Transactions on Algorithms10.1145/315530114:1(1-35)Online publication date: 3-Jan-2018
https://dl.acm.org/doi/10.1145/3155301
Eenberg KLarsen KYu HHatami HMcKenzie PKing V(2017)DecreaseKeys are expensive for external memory priority queuesProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055437(1081-1093)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055437
Show More Cited By

View Options

Get Access

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents