Improved fast integer sorting in linear space

ABSTRACT

We present improved fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in linear space in &Ogr;(n log log n log log log n) time. This improves the &Ogr;(n(log log n)^3/2) time bound given in [6]. When the n integers in {0,1,…, m - 1} to be sorted satisfying log m ⪈(log n)²+∈, 0 < ∈ < 1, the time complexity for sorting can be further reduced to &Ogr;(n log log n). These results are obtained by applying signature sorting on our previous result[6].

REFERENCES

• 1: 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
• 2: 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]
• 3: P. van Emde Boas, R. Kaas, E. Zijlstra, Design and implementation of an efficient priority queue, Math. Syst. Theory 10 99-127(1977).
• 4: 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]
• 5: 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]
• 6: 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
• 7: 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
• 8: Yijie Han , Xiaojun Shen, Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.419-428, January 17-19, 1999, Baltimore, Maryland, United States
• 9: D. Kirkpatrick and S. Reisch, Upper bounds for sorting integers on random access machines, Theoretical Computer Science 28, 263-276(1984).
• 10: 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
• 11: 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
• 12: 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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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