Burstsort

From Wikipedia, the free encyclopedia

Burstsort and its variants are cache-efficient algorithms for sorting strings and are faster than quicksort and radix sort for large data sets.

Burstsort algorithms use tries to store prefixes of strings, with binary search trees as end nodes containing sorted, unique, suffixes.

[edit] References

• The original burstsort article: Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries
• A burstsort derivative (C-burstsort), faster than burstsort: Cache-Efficient String Sorting Using Copying
• The data type used in burstsort: Burst Tries: A Fast, Efficient Data Structure for String Keys
• Efficient Trie-Based Sorting of Large Sets of Strings
• A burstsort implementation in C++: Free C++ Copy-Burstsort Library

v • d • e Sorting algorithms Theory Computational complexity theory | Big O notation | Total order | Lists | Stability | Comparison sort Exchange sorts Bubble sort | Cocktail sort | Odd-even sort | Comb sort | Gnome sort | Quicksort Selection sorts Selection sort | Heapsort | Smoothsort | Strand sort Insertion sorts Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting Merge sorts Merge sort Non-comparison sorts Radix sort | Bucket sort | Counting sort | Pigeonhole sort | Tally sort Others Topological sorting | Sorting network | Bitonic sorter Ineffective/jokeful sorts Bogosort