Sorting in Linear Time?
Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman · Journal of Computer and System Sciences · 1995
We show that a unit-cost RAM with a word length of w bits can sort n integers in the range O. .2W -1 in O (n log log n) time, for arbitrary w z log n, a significant improvement over the bound of O (n-) achieved by the fusion trees of Fredman and Willard.Provided that w 2 (log n)z+', for some fixed e > 0, the sorting can even be accomplished in linear expected time with a randomized algorithm.Both of our algorithms parallelize without loss on a unitcost PRAM with a word length of w bits.The first one yields an algorithm that uses O (log n) time and O (n log log n) operations on a deterministic CRCW PRAM.The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w 2 (log n)2+' for some fixed c >0.Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.