Burstsort
Burstsort is a cache-efficient, trie-based string sorting algorithm invented by Ranjan Sinha and Justin Zobel (2004) that partitions strings into small buckets inside a dynamic burst trie before sorting each leaf bucket in L1/L2 CPU cache.
Burstsort is a high-speed, cache-aware string sorting algorithm introduced by Ranjan Sinha and Justin Zobel in 2004 (building on Heinz, Zobel, and Williams's burst trie data structure). Standard comparison-based sorting algorithms such as quicksort or mergesort perform poorly on large collections of variable-length strings because comparing long shared prefixes repeatedly dereferences scattered string pointers, causing heavy CPU cache misses. Even classic MSD radix sort suffers from high memory overhead when allocating 256-way branch tables at every character depth.
Burstsort overcomes both bottlenecks by dynamically building a burst trie: strings are inserted by their leading characters into small, flat leaf buckets (typically capped at 4,096โ8,192 strings). Only when a bucket overflows does it "burst" into a 256-way (or alphabet-sized) trie node and redistribute its contents one character deeper. Once all strings are distributed, every small leaf bucket fits comfortably inside L1/L2 CPU cache and is sorted rapidly using multikey quicksort or MSD radix sort, making Burstsort one of the fastest known algorithms for sorting millions of natural-language words, URLs, or genomic sequences.
Algorithmic Phases: Insertion, Bursting, and Traversal
Burstsort executes in two clean phases over an array of N string pointers:
- Trie construction & dynamic bursting:
- Start with a single empty root bucket (a dynamic array of string pointers).
- Scan each string from character depth d = 0. Follow existing trie nodes until reaching a leaf bucket at depth d, and append the string pointer (or a short suffix copy in C-Burstsort) to that bucket.
- Whenever a bucket's size exceeds a fixed burst threshold B (for example, B = 8,192), allocate a new internal trie node indexed by character c at depth d, redistribute the bucket's B pointers into child buckets for each distinct character (handling end-of-string terminators separately), and free the old bucket.
- In-order bucket sorting and collection:
- Perform an in-order depth-first traversal of the burst trie.
- At each non-empty leaf bucketโwhose strings already share an identical d-character prefixโsort the small bucket in place starting at character offset d using multikey quicksort (three-way radix quicksort), then write the sorted pointers sequentially into the output array.
| String Sorting Algorithm | Prefix Comparison Overhead | Memory Footprint | Cache Locality | Empirical Speed on Large String Sets |
|---|---|---|---|---|
| Burstsort / C-Burstsort | Eliminated for shared prefixes | Moderate (grows only on dense buckets) | Very high (L1/L2-sized buckets + suffix copying) | Fastest on 106โ108 strings |
| Multikey Quicksort | Re-scans shared prefixes at pivots | O(1) extra pointer space | Moderate (random pointer chasing) | Fast baseline, ~2ร slower than Burstsort |
| MSD Radix Sort | Eliminated per character | High (256-slot arrays per node) | Poor on sparse small subarrays | Fast for small alphabets; memory-heavy |
| Standard Quicksort (strcmp) | Full rescan from index 0 on every comparison | O(log N) stack | Poor (heavy pointer dereferencing) | Slowest on long shared prefixes |
C-Burstsort and In-Place Engineering Variants
In the original pointer-based Burstsort (P-Burstsort), sorting the final leaf buckets still required dereferencing scattered heap pointers to read suffixes. Sinha, Zobel, and Wirth subsequently developed C-Burstsort (Copying Burstsort)โwhich copies the remaining string suffixes contiguously into each bucket's flat memory buffer so multikey quicksort scans sequential bytes in L1 cacheโand in-place Burstsort, which reuses the input pointer array to cut peak auxiliary memory while matching C-Burstsort throughput. Benchmark evaluations across multi-million-word text corpora, genomic k-mer indices, and web URL datasets consistently show that C-Burstsort reduces L2 cache misses by more than an order of magnitude compared with standard pointer-based quicksort, often achieving 2ร to 4ร speedups on large string collections with long shared prefixes.
Frequently Asked Questions
Why is Burstsort faster than standard quicksort for sorting strings? Standard quicksort compares strings from their first character on every comparison and jumps randomly across memory pointers; Burstsort consumes shared prefixes once via trie branching and sorts small, cache-resident buckets starting past the shared prefix.
What does "bursting" mean in Burstsort? Each leaf of the burst trie starts as a flat list of strings; when a list grows larger than a chosen threshold (such as 8,192 strings), it "bursts" into a trie node that splits those strings into smaller sub-buckets based on their next character.
What algorithm sorts the individual buckets at the end of Burstsort? Once all strings are partitioned into small leaf buckets, Burstsort typically sorts each bucket from the current character depth onward using multikey quicksort (three-way string quicksort).
References
- Sinha, R., & Wirth, A.. Engineering Burstsort: Towards Fast In-Place String Sorting. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-540-68552-4_2
- Sinha, R., & Wirth, A. (2010). Engineering burstsort. ACM Journal of Experimental Algorithmics. https://doi.org/10.1145/1671970.1671978
- Sinha, R., et al. (2007). Cache-efficient string sorting using copying. ACM Journal of Experimental Algorithmics. https://doi.org/10.1145/1187436.1187439