Spreadsort: Mechanism, Complexity Analysis & Interactive Visualizer

Spreadsort

A state-of-the-art hybrid distribution sort: combines bucket partitioning based on key bits with standard comparison algorithms for small bins, outperforming Quicksort on many datasets.

How it works

Spreadsort, designed by Steven J. Ross in 2002, is a high-speed hybrid algorithm included in the Boost C++ libraries. It integrates radix/bucket distribution sorting with comparison sorting:

1. Range & Bin Size Calculation: Scan the array to find the minimum and maximum keys. Compute a distribution threshold and select a bin count \(K\) based on the array size and key ranges.
2. Distribution Phase: Partition the input array into \(K\) buckets using the most significant bits or proportional divisions of the elements' key values.
3. Adaptive Recursion:
   • If a bucket contains elements with a large range of values, recursively apply Spreadsort to that bucket.
   • If a bucket size is small or the range of values is tight, switch to a fast comparison-based sort (like Insertion Sort or standard Quicksort).

Complexity

Interactive visualization

Pseudocode

procedure spreadsort(A):
  n ← length(A)
  if n < threshold:
    comparisonSort(A)
    return
    
  minVal, maxVal ← findMinMax(A)
  if minVal == maxVal:
    return
    
  K ← calculateBucketCount(n)
  buckets ← array of K empty lists
  
  for each x in A:
    idx ← getBucketIndex(x, minVal, maxVal, K)
    buckets[idx].append(x)
    
  A ← empty
  for each bucket in buckets:
    spreadsort(bucket)  # Recurse or fallback to insert sort
    A.appendAll(bucket)

JavaScript implementation

function spreadsort(arr) {
  const n = arr.length;
  if (n < 16) {
    // fallback to insertion sort for small partitions
    for (let i = 1; i < n; i++) {
      let key = arr[i];
      let j = i - 1;
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
    return arr;
  }
  
  let min = arr[0], max = arr[0];
  for (let x of arr) {
    if (x < min) min = x;
    if (x > max) max = x;
  }
  if (min === max) return arr;
  
  const K = Math.floor(n / 4) || 2;
  const buckets = Array.from({ length: K }, () => []);
  const range = max - min;
  
  for (let x of arr) {
    const idx = Math.min(K - 1, Math.floor(((x - min) / range) * K));
    buckets[idx].push(x);
  }
  
  let current = 0;
  for (let b = 0; b < K; b++) {
    spreadsort(buckets[b]);
    for (let x of buckets[b]) {
      arr[current++] = x;
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Large datasets of numeric/string keys: Highly recommended when sorting huge integer, float, or structured keys with uniform properties.
• Generic object sorting: Avoid when sorting objects based on complex comparisons that cannot be mapped easily to distribution divisions.