Sorting in Linear Time?

摘要

We show that a unit-cost RAM with a word length ofwbits can sortnintegers in the range 0…2w−1 inO(n log log n) time for arbitraryw⩾log n, a significant improvement over the bound ofO(n logn) achieved by the fusion trees of Fredman and Willard. Provided thatw⩾(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 ofwbits. The first one yields an algorithm that usesO(log n) time andO(n log log n) operations on a deterministic CRCW PRAM. The second one yields an algorithm that usesO(log n) expected time andO(n) expected operations on a randomized EREW PRAM, provided thatw⩾(log n)2+εfor some fixedε>0. Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting of multiple-precision integers represented in several words.