Sorting in linear time?
1998 (English)In: Journal of Computer and System Sciences, Vol. 57, 74-93 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
1998. Vol. 57, 74-93 p.
IdentifiersURN: urn:nbn:se:uu:diva-25784OAI: oai:DiVA.org:uu-25784DiVA: diva2:53558