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

ABSTRACT

We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2, &1dots;, 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^&egr;) 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: Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Information and Computation, v.136 n.1, p.25-51, July 10, 1997 [doi>10.1006/inco.1997.2632]
• 2: A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
• 3: 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 [doi>10.1145/225058.225173]
• 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: Martin Dietzfelbinger , Torben Hagerup , Jyrki Katajainen , Martti Penttonen, A reliable randomized algorithm for the closest-pair problem, Journal of Algorithms, v.25 n.1, p.19-51, Oct. 1997 [doi>10.1006/jagm.1997.0873]
• 6: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 7: Torben Hagerup , H. Shen, Improved nonconservative sequential and parallel integer sorting, Information Processing Letters, v.36 n.2, p.57-63, Oct. 1990 [doi>10.1016/0020-0190(90)90097-H]
• 8: Yijie Han, Improved fast interger sorting in linear space, Information and Computation, v.170 n.1, p.81-94, October 10, 2001 [doi>10.1006/inco.2001.3053]
• 9: Yijie Han, Fast Integer Sorting in Linear Space, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.242-253, February 01, 2000
• 10: Y. Han, M. Thorup. Sorting integers in O(n√ \over loglog n) expected time and linear space. Manuscript.
• 11: Yijie Han , Xiaojun Shen, Conservative Algorithms for Parallel and Sequential Integer Sorting, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.324-333, August 24-26, 1995
• 12: D. Kirkpatrick and S. Reisch. Upper bounds for sorting integers on random access machines. Theoretical Computer Science 28, 263--276(1984).
• 13: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 14: Rajeev Raman, Priority Queues: Small, Monotone and Trans-dichotomous, Proceedings of the Fourth Annual European Symposium on Algorithms, p.121-137, September 25-27, 1996
• 15: Mikkel Thorup, Faster deterministic sorting and priority queues in linear space, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.550-555, January 25-27, 1998, San Francisco, California, United States
• 16: Mikkel Thorup, Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.352-359, January 05-07, 1997, New Orleans, Louisiana, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
algorithms, integer sorting, linear space, sorting, time complexity