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+e
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 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+e
for some fixed e > 0.
Our deterministic and randomized sequential
and parallel algorithms generalize to the
lexicographic sorting problem of sorting
multiple-precision integers represented
in several words.
Journal of Computer and System Sciences,
57:74-93, 1998.
Complete text:
ps,
pdf
|