A new efficient radix sort
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 714-721
- https://doi.org/10.1109/sfcs.1994.365721
Abstract
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).<>Keywords
This publication has 10 references indexed in Scilit:
- Using difficulty of prediction to decrease computation: fast sort, priority queue and convex hull on entropy bounded inputsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Three Partition Refinement AlgorithmsSIAM Journal on Computing, 1987
- Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ TimeSIAM Journal on Computing, 1985
- Asymptotical Growth of a Class of Random TreesThe Annals of Probability, 1985
- Data Structures and Algorithms 1Published by Springer Nature ,1984
- Upper bounds for sorting integers on random access machinesTheoretical Computer Science, 1983
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Sorting by distributive partitioningInformation Processing Letters, 1978
- The complexity of searching an ordered random tablePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- Trie memoryCommunications of the ACM, 1960