Improved fast integer sorting in linear space
Yijie Han · Symposium on Discrete Algorithms · 2001
We present improved fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in linear space in O(n log log n log log log n) time. This improves the O(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 g(log n)2+∈, 0