Sorting in linear time?

Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman

We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0..2w-1 in O(n log log n) time, for arbitrary w ≥ log n, a significant improvement over the bound of O(n sqrt(log n)) achieved by the fusion trees of Fredman and Willard. Provided that w ≥ (log n)2+ε for some fixed ε > 0, the sorting can even be accomplished in linear expected time with a randomized algorithm.

Both of our algorithms parallelize without loss on a unit-cost 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 ≥ (log n)2+ε for some fixed ε > 0.

Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.