A New Efficient Radix Sort

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). >

Authors

• Arne Andersson
• Stefan Nilsson

Keywords

• Sorting
• Costs
• Partitioning algorithms
• Entropy
• Computer science
• Algorithm design and analysis
• Interpolation
• Gaussian distribution
• Radix Sort
• Binary String
• Stationary Process
• Lexicographic
• Sorting Algorithm
• Sorts Of Problems
• Time Constant
• Time Complexity
• Groups In Order
• Linear Time
• Word Length
• Basic Algorithm
• Compression Rate
• Forward Algorithm
• Backward Algorithm
• Number Of Strings
• Alphabet Size
• Input String
• Asymptotic Complexity