Burstsort: Mechanism, Complexity Analysis & Interactive Visualizer

Burstsort

A state-of-the-art string-based sorting algorithm: dynamically builds a trie with leaf-level buckets, "bursting" buckets into sub-tries when they grow too large, followed by a fast comparison sort sweep.

How it works

Burstsort, developed by Heinz Sinha and Alistair Moffat in 2003, is designed to resolve the cache-miss issues inherent in traditional Radix sorts on strings. Instead of building a full trie structure (which scatters memory and causes cache misses), Burstsort uses an adaptive hybrid structure:

1. Trie with Buckets: Build a shallow trie structure where the leaf nodes are not individual keys, but growable arrays (buckets) of string elements sharing a common prefix.
2. Insertion & Growth: Traverse the input strings. Use their characters to traverse the trie to the correct leaf bucket. Append the string to that bucket.
3. The Burst Step: If a bucket's size exceeds a limit (the "burst threshold"), the bucket is *burst* (dissolved). It is replaced by a new trie node representing the next character, and its elements are redistributed into new, empty child buckets.
4. Cleanup sorting: Once all strings are distributed, traverse the trie leaves in-order. Sort each small bucket individually using a cache-friendly comparison sort (like Insertion Sort or Quicksort).

Complexity

Interactive visualization

Pseudocode

procedure burstsort(Strings):
  root ← new TrieNode()
  
  for each str in Strings:
    bucket ← traverseToBucket(root, str)
    bucket.append(str)
    if bucket.size > threshold:
      burst(bucket)
      
  output ← empty list
  traverseAndSort(root, output)
  return output

procedure traverseAndSort(node, output):
  for each child in node.children:
    if child is Bucket:
      insertionSort(child)
      output.appendAll(child)
    else:
      traverseAndSort(child, output)

JavaScript implementation

// Simple demonstration of string-based Burstsort
class BurstTrieNode {
  constructor() {
    this.children = {}; 
    this.isBucket = true;
    this.bucketItems = [];
  }
}

function burstsort(arr) {
  const root = new BurstTrieNode();
  const threshold = 32;
  
  // Helper to insert a string into the trie
  function insert(node, str, charIdx) {
    if (!node.isBucket) {
      const char = str[charIdx] || "";
      if (!node.children[char]) node.children[char] = new BurstTrieNode();
      insert(node.children[char], str, charIdx + 1);
      return;
    }
    
    node.bucketItems.push(str);
    if (node.bucketItems.length > threshold) {
      // Burst the bucket
      node.isBucket = false;
      const items = node.bucketItems;
      node.bucketItems = [];
      for (let item of items) {
        const char = item[charIdx] || "";
        if (!node.children[char]) node.children[char] = new BurstTrieNode();
        node.children[char].bucketItems.push(item);
      }
    }
  }
  
  for (let str of arr) {
    insert(root, str, 0);
  }
  
  let i = 0;
  function traverse(node) {
    if (node.isBucket) {
      // sort bucket stably
      node.bucketItems.sort(); 
      for (let item of node.bucketItems) {
        arr[i++] = item;
      }
      return;
    }
    const keys = Object.keys(node.children).sort();
    for (let k of keys) {
      traverse(node.children[k]);
    }
  }
  
  traverse(root);
  return arr;
}

Pros and cons

When (not) to use it

• Large-scale text databases: Best choice for sorting huge lists of URLs, names, words, or hex strings.
• Numbers and primitives: Avoid for regular numbers or general arrays of structures; standard Quicksort or Timsort is easier and faster.