(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
We show that a unit-cost RAM with a word
length of w bits can sort n integers
in the range 0 .. 2^(w-1) in
O(n loglog 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+epsilon)
for some fixed epsilon>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 loglog 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+epsilon)
for some fixed epsilon>0.
Our deterministic and randomized sequential
and parallel algorithms generalize to the
lexicographic sorting problem of sorting
multiple-precision integers represented
in several words.