Burstsort

Burstsort
Class	Sorting algorithm
Data structure	Trie
Worst case performance	$O (wn)$
Worst case space complexity	$O (wn)$

Burstsort and its variants are cache-efficient algorithms for sorting strings and are faster than radix sort for large data sets of common strings, 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.

Burstsort was introduced as a sort that is similar to MSD Radix Sort,^[1] but is faster due to being aware of caching and related radixes being stored closer to each other due to specifics of trie structure. It exploits specifics of strings that are usually encountered in real world. And even though asymptotically it is the same as radix sort, with time complexity of $O (wn)$ (w - word length and n - number of strings to be sorted), but due to more optimal memory distribution it tends to be twice as fast on big data sets of strings.

References

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

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
Engineering Burstsort: Towards Fast In-Place String Sorting

External links

A burstsort implementation in C++: Free C++ Copy-Burstsort Library
A burstsort implementation in Java: burstsort4j
Judy arrays are a type of copy burstsort: C implementation

Sorting algorithms

Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort

Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Quicksort Stooge sort Bogosort

Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort

Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting

Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort

Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Pigeonhole sort Proxmap sort Radix sort Flashsort

Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network

Hybrid sorts	Block sort Timsort Introsort Spreadsort

Other	Topological sorting Pancake sorting Spaghetti sort

This article is issued from Wikipedia - version of the Friday, November 13, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.