- Burstsort
Burstsort and its variants are cache-efficient algorithms for sorting strings and are faster than
quicksort andradix sort for largedata set s.Burstsort algorithms use tries to store prefixes of strings, with
binary search trees as end nodes containing sorted, unique, suffixes.References
* The original burstsort article: [http://www.cs.rmit.edu.au/~jz/fulltext/alenex03.pdf Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries]
* A burstsort derivative (C-burstsort), faster than burstsort: [http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf Cache-Efficient String Sorting Using Copying]
* The data type used in burstsort: [http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf Burst Tries: A Fast, Efficient Data Structure for String Keys]
* [http://goanna.cs.rmit.edu.au/~jz/fulltext/acsc03sz.pdf Efficient Trie-Based Sorting of Large Sets of Strings]
* A burstsort implementation in C++: [http://sourceforge.net/projects/burstsort/ Free C++ Copy-Burstsort Library]
Wikimedia Foundation. 2010.