Burstsort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Burstsort
Class Sorting algorithm
Data structure Array
Worst case performance O(n\log(n))

Burstsort and its variants are cache-efficient algorithms for sorting strings and are faster than quicksort for large data sets, first published in 2003.[1]

Burstsort algorithms use a trie to store prefixes of strings, with growable arrays of pointers as end nodes containing sorted, unique, suffixes (referred to as buckets). Some variants copy the string tails into the buckets. As the buckets grow beyond a predetermined threshold, the buckets are "burst", giving the sort its name. A more recent variant uses a bucket index with smaller sub-buckets to reduce memory usage. Most implementations delegate to multikey quicksort, an extension of three-way radix quicksort, to sort the contents of the buckets. By dividing the input into buckets with common prefixes, the sorting can be done in a cache-efficient manner.

References[edit]

  1. ^ Sinha, R.; Zobel, J. (2005). "Cache-conscious sorting of large sets of strings with dynamic tries". Journal of Experimental Algorithmics 9: 1.5. doi:10.1145/1005813.1041517.  edit

External links[edit]