Sorting in linear time?

Sorting in linear time?,10.1145/225058.225173,Arne Andersson,Torben Hagerupt,Stefan Nilsson,Rajeev Raman

Sorting in linear time?   (Citations: 88)
BibTex | RIS | RefWorks Download
We show that a unit-cost RAM with a word length of bits can sort integers in the range in time, for arbitrary , a significant improvement over the bound of achieved by the fusion trees of Fredman and Willard. Provided that , for some fixed , 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 bits. The firstone yields an algorithm that uses time and op- erations on a deterministic CRCW PRAM. The second one yields an algorithm that uses expected time and expected operations on a randomized EREW PRAM, provided that for some fixed . Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.
Conference: ACM Symposium on Theory of Computing - STOC , pp. 427-436, 1995
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: