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 radix sorting so as to achieve good worst-case running time without sacrificing average-case performance. Our implementations are competitive with the best previously published string sorting programs.

Full paper (postscript)
Full paper (pdf)
Code (At Stefan Nilsson's home page)