Sorting in Linear Time?

✍ Scribed by Arne Andersson; Torben Hagerup; Stefan Nilsson; Rajeev Raman

• Book ID: 102971739
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 679 KB
• Volume: 57
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1580

✦ Synopsis

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 log log n) time for arbitrary w log n, a significant improvement over the bound of O(nlog n) achieved by the fusion trees of Fredman and Willard. Provided that w (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 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+= 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.