Implementing radixsort

ABSTRACT

We present and evaluate several optimization and implementation techniques for string sorting. In particular, we study a recently published radix sorting algorithm, Forward radixsort, that has a provably good worst-case behavior. Our experimental results indicate that radix sorting is considerably faster (often more than twice as fast) than comparison-based sorting methods. This is true even for small input sequences. We also show that it is possible to implement a radixsort with good worst-case running time without sacrificing average-case performance. Our implementations are competitive with the best previously published string sorting programs.

REFERENCES

• 1: ANDERSSON, A. AND NILSSON, S. 1994. A new efficient radix sort. In <i>Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science</i> (1994), pp. 714-721.
• 2: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 3: Jon L. Bentley , M. Douglas McIlroy, Engineering a sort function, Software—Practice & Experience, v.23 n.11, p.1249-1265, Nov. 1993 [doi>10.1002/spe.4380231105]
• 4: Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: DAVIS, I. J. 1992. A fast radix sort. <i>The Computer Journal 35</i>, 6, 636-642.
• 7: Luc Devroye, Lecture Notes on Bucket Algorithms, Birkhauser Boston, 1986
• 8: DOBOSIEWICZ, W. 1978. Sorting by distributive partitioning. <i>Information Processing Letters 7</i>, 1, 1-6.
• 9: EHRLICH, G. 1981. Searching and sorting real numbers. <i>Journal of Algorithms 2</i>, 1, 1-12.
• 10: Jeffrey H. Kingston, Algorithms and Data Structures: Design, Correctness, Analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 11: MCILROY, P. M., BOSTIC, K., AND MCILROY, M. D. 1993. Engineering radix sort. <i>Computing Systems 6</i>, 1, 5-27.
• 12: MEHLHORN, K. 1984. <i>Sorting and Searching</i>, Volume 1 of <i>Data Structures and Algorithms</i>. Springer-Verlag.
• 13: Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
• 14: TAMMINEN, M. 1983. Analysis of N-trees. <i>Information Processing Letters 16</i>, 3, 131-137.
• 15: TAMMINEN, M. 1985. Two levels are as good as any. <i>Journal of Algorithms 6</i>, 1, 138-144.
• 16: THE UNICODE CONSORTIUM. 1991. <i>The Unicode Standard: Worldwide Character Encoding. Version 1.0</i>, Volume 1 and 2. Addison-Wesley.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Experimentation, Performance

Keywords:
adaptive radixsort, algorithms, forward radixsort, radix sorting, sorting, string sorting