Improved Fast Integer Sorting in Linear Space

AbstractWe 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 log log log n) time. When log m≥log2+ϵn, ϵ>0, we can further achieve O(n log log n) time. This improves the O(n(log log n)2) time bound given in M. Thorup (1998) in “Proc. 1998 ACM-SIAM Symp. on Discrete Algorithms (SODA'98),” pp. 550–555). This result is obtained by combining our new technique with that of Thorup's. Signature sorting (A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, 1995, in “Proc. 1995 Symposium on Theory of Computing,” pp. 427–436), A. Andersson's result (1996, in “Proc. 1996 IEEE Symp. on Foundations of Computer Science,” pp. 135–141), R. Raman's result (1996, Lecture Notes in Computer Science, Vol. 1136, pp. 121–137, Springer-Verlag Berlin/New York), and our previous result (Y. Han and X. Shen, 1999, in “Proc. 1999 Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99),” Baltimore, MD, January, pp. 419–428) are also used for the design of our algorithms. We provide an approach and techniques which are totally different from previous approaches and techniques for the problem. As a consequence our technique can be extended to apply to nonconservative sorting and parallel sorting. Our nonconservative sorting algorithm sorts n integers in {0, 1, …, m−1} in time O(n(log log n)2/(log k+log log log n)) using word length k log(m+n), where k≤log n. Our EREW parallel algorithm sorts n integers in {0, 1, …, m−1} in O((log n)2) time and O(n(log log n)2/log log log n) operations provided log m=Ω((log n)2)