โ† Wiki Index / Computation & Algorithms / Burstsort
๐Ÿ’ป Computation & Algorithms

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:

  1. 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.
  2. 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 AlgorithmPrefix Comparison OverheadMemory FootprintCache LocalityEmpirical Speed on Large String Sets
Burstsort / C-BurstsortEliminated for shared prefixesModerate (grows only on dense buckets)Very high (L1/L2-sized buckets + suffix copying)Fastest on 106โ€“108 strings
Multikey QuicksortRe-scans shared prefixes at pivotsO(1) extra pointer spaceModerate (random pointer chasing)Fast baseline, ~2ร— slower than Burstsort
MSD Radix SortEliminated per characterHigh (256-slot arrays per node)Poor on sparse small subarraysFast for small alphabets; memory-heavy
Standard Quicksort (strcmp)Full rescan from index 0 on every comparisonO(log N) stackPoor (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

  1. 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
  2. Sinha, R., & Wirth, A. (2010). Engineering burstsort. ACM Journal of Experimental Algorithmics. https://doi.org/10.1145/1671970.1671978
  3. Sinha, R., et al. (2007). Cache-efficient string sorting using copying. ACM Journal of Experimental Algorithmics. https://doi.org/10.1145/1187436.1187439
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision