The ACM Journal of Experimental Algorithmics

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.

• Keywords: Algorithms, Sorting, String sorting, Radix sorting, Adaptive radixsort, forward radixsort
• CR Categories: F.2.2 [Theory of Computation]: Nonnumerical Algorithms and Problems
• Sources:
  
  • The LaTeX version of the article; this is a Unix tar file that contains the LaTeX sources; note that you must be a subscriber (institutional or individual) to access this file.
  • The Postscript version or PDF version of the article;
    note that you must be a subscriber (institutional or individual) to access these files.
  • The HTML version of the article;
    note that you must be a subscriber (institutional or individual) to access this file.
  • The software suite accompanying the article; this is a small Unix tar file, which includes the source code, a Makefile, and the test files used in the article.
  • The bibliography given in the article.

Last updated and validated January 6, 1999, by editor@jea.acm.org