Deterministic sorting in O(nlog log n) 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 [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 ( n log log n ) time but uses O ( m ε ) space. Our results can also be compared with Thorup's previous result [16] which sorts in O ( n log log n ) time and linear space but uses randomization.

Authors

• Yijie Han

Keywords

• algorithms
• integer sorting
• linear space
• sorting
• time complexity