Deterministic sorting in O ( n log log n ) time and linear space
Yijie Han · 2002
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(me) 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.