Stefan Nilsson

STOC Conference 1995 Conference Paper

Sorting in linear time?

• Arne Andersson
• Torben Hagerup
• Stefan Nilsson
• Rajeev Raman

FOCS Conference 1994 Conference Paper

A New Efficient Radix Sort

• Arne Andersson
• Stefan Nilsson

We present new improved algorithms for the sorting problem. The algorithms are not only efficient but also clear and simple. First, we introduce Forward Radix Sort which combines the advantages of traditional left-to-right and right-to-left radix sort in a simple manner. We argue that this algorithm will work very well in practice. Adding a preprocessing step, we obtain an algorithm with attractive theoretical properties. For example, n binary strings can be sorted in /spl Theta/ (n log(B/(n log n)+2)) time, where B is the minimum number of bits that have to be inspected to distinguish the strings. This is an improvement over the previously best known result by Paige and Tarjan (1987). The complexity may also be expressed in terms of H, the entropy of the input: n strings from a stationary ergodic process can be sorted in /spl Theta/ (n log(1/H+1)) time an improvement over the result recently presented by Chen and Reif (1993). >