SORTING IN LINEAR-TIME

We show that a unit-cost RAM with a word length of w bits can sort n i ntegers in the range 0 ... 2(w)-1 in O(n log log n) time for arbitrary w greater than or equal to log n, a significant improvement over the bound of O(n root log n) achieved by the fusion trees of Fredman and W illard. Provided that w greater than or equal to (log n)(2+epsilon) fo r some fixed epsilon> 0. the sorting can even be accomplished in linea r expected time with a randomized algorithm. Both of our algorithms pa rallelize without loss on a unit-cost PRAM with a word length of w bit s. The first one yields an algorithm that uses O(log n) time and O(n l og log n) operations on a deterministic CRCW PRAM. The second one yiel ds an algorithm that uses O(log n) expected time and O(n) expected ope rations on a randomized EREW PRAM, provided that w greater than or equ al to (log n)(2+epsilon) for some fixed epsilon > 0. Our deterministic and randomized sequential and parallel algorithms generalize to the l exicographic sorting of multiple-precision integers represented in sev eral words. (C) 1998 Academic Press.