Burstsort

Burstsort is a family of string sorting algorithms designed to make good use of the processor cache. It is a relative of radix sort, but instead of repeatedly partitioning the whole data set by character it inserts each string into a trie whose leaves are growable arrays of pointers, called buckets, that hold the remaining suffixes of strings sharing a common prefix. When a bucket grows past a set threshold it is burst into a new level of the trie, which gives the method its name, and the contents of small buckets are finally sorted with a method such as multikey quicksort. Because strings with common prefixes are kept close together in memory, the algorithm causes far fewer cache misses than comparison sorts on large collections of ordinary strings. It was first published in 2003, and its source gives a running time of O(wn) for n strings of word length w, the same asymptotic bound as radix sort, while reporting that in practice it tends to be about twice as fast on big data sets of strings.