Efficient Trie-Based Sorting of Large Sets of Strings

Sinha, R. and Zobel, J.

    Sorting is a fundamental algorithmic task. Many general purpose sorting algorithms have been developed, but efficiency gains can be achieved by designing algorithms for specific kings of data, such as strings. In previous work we have shown that our burstsort, a trie-based algorithm for sorting strings, is for large data sets more efficient than al previous algorithms for this task. In this paper we re-evaluate some of the implementation details of burstsort, in particular the method for managing buckets held at leaves. We show that better choice of data structures further improves the efficiency, at a small additional cost in memory. For sets of around 30,000,000 strings, our improved burstsort is nearly twice as fast as the previous best sorting algorithm.
Cite as: Sinha, R. and Zobel, J. (2003). Efficient Trie-Based Sorting of Large Sets of Strings. In Proc. Twenty-Sixth Australasian Computer Science Conference (ACSC2003), Adelaide, Australia. CRPIT, 16. Oudshoorn, M. J., Ed. ACS. 11-18.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS