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.
%0 Journal Article
%1 297136
%A Andersson, Arne
%A Nilsson, Stefan
%C New York, NY, USA
%D 1998
%I ACM
%J J. Exp. Algorithmics
%K 2010 kde radixsort seminar sorting
%P 7
%R 10.1145/297096.297136
%T Implementing radixsort
%U http://portal.acm.org/citation.cfm?id=297096.297136&coll=Portal&dl=GUIDE&CFID=91751722&CFTOKEN=47888703
%V 3
%X 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.
@article{297136,
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.},
added-at = {2010-05-26T23:29:25.000+0200},
address = {New York, NY, USA},
author = {Andersson, Arne and Nilsson, Stefan},
biburl = {https://www.bibsonomy.org/bibtex/2c24c95adfdfc4f37ef6d24f6172d1b6f/redw0lf},
description = {Implementing radixsort},
doi = {10.1145/297096.297136},
interhash = {43a6547ff0acafe88c89a8a4ab6ff67f},
intrahash = {c24c95adfdfc4f37ef6d24f6172d1b6f},
issn = {1084-6654},
journal = {J. Exp. Algorithmics},
keywords = {2010 kde radixsort seminar sorting},
pages = 7,
publisher = {ACM},
timestamp = {2010-05-26T23:29:25.000+0200},
title = {Implementing radixsort},
url = {http://portal.acm.org/citation.cfm?id=297096.297136&coll=Portal&dl=GUIDE&CFID=91751722&CFTOKEN=47888703},
volume = 3,
year = 1998
}