Cairn

algorithms · sorting · O(n) average (measured), O(n²) adversarial worst case · hybrid distribution + comparison, recursive, in-place, unstable

↩ back to Non-Comparison Sorts

Spreadsort

Spreadsort (Steven Ross, 2002; shipped in Boost as boost::sort::spreadsort) starts from the same move as bucket sort and Flash Sort: classify values into buckets by an arithmetic formula over the data's own min/max, instead of comparing values pairwise. Where it genuinely differs is what happens to a bucket that's still too big to finish cheaply. Bucket sort finishes every bucket with a plain comparison sort no matter its size; Flash Sort finishes the whole array with one flat insertion-sort pass once classes are grouped. Both of those pay for it on a skewed input — bucket sort's own pitfalls and Flash Sort's own complexity section each measured the identical failure mode: values crammed into one oversized bucket collapse to plain O(n²) insertion sort inside it, no matter how well everything else spread out. Spreadsort's fix is to treat an oversized bucket as its own new sorting problem: recompute min/max local to just that bucket, then repeat the classify-and-permute step instead of finishing it — falling back to a real comparison sort only once a region is small enough that another distribution pass isn't worth the overhead. That's the whole idea: the same in-place swap-chain permutation as Flash Sort, applied recursively to whichever sub-range still needs it, with the classification bounds re-tightened at every level.

Try it

Enter a comma-separated list of integers, positive or negative (this demo caps it at 10 values). Each region starts by scanning its own local min/max (not the whole array's), then classifies every value in that region into one of m buckets via floor((m-1) × (v-min) / (max-min)), fixes bucket boundaries, and permutes in place (bordered bar is the index being examined, solid bar is its swap partner, the thin dark line marks a bucket boundary) — the same three steps Flash Sort uses. What happens next is the difference: any bucket still bigger than a small threshold (3, for this demo — the reference implementation below uses 8) becomes its own region and repeats the whole process with its own freshly narrowed min/max, shown dimmed while it waits its turn; a bucket at or under the threshold finishes right there with a plain insertion-sort pass (accent bar is the "hole" being carried left) instead of waiting for the rest of the array. Finished regions turn the same tan as a fully sorted bar.

Why it works

Every region Spreadsort works on carries its own [lo, hi) index range, and the very first thing it does with that range is scan only those indices for a fresh min and max — never reusing a parent region's bounds, and never the whole array's. That local narrowing is the entire mechanism: once a value range has been handed to a region of its own, the classification formula only has to spread that range's values across m buckets, not the full array's, so a cluster that looked hopeless at the top level (everything packed into one bucket, the exact failure both siblings above hit) becomes an ordinary, roughly-uniform-looking input one level down — because by definition, every value still in play shares a narrow local min/max now. Recursing on exactly the bucket that absorbed too much, rather than trying to fix the classification formula itself, sidesteps the problem structurally: a bad distribution at one level doesn't get to compound into a citywide comparison-sort meltdown, it just triggers one more level of the same cheap classify step, scoped tighter each time.

The base case matters just as much as the recursive step. Two conditions stop a region from recursing forever: its size drops to the threshold or below (small enough that a plain comparison sort finishes it faster than another distribution pass would), or its local min equals its local max (every remaining value is identical — nothing left to distribute). Skip either check and the recursion either does needless work forever on a bucket of one repeated value, or never terminates at all; both are checked directly in Pitfalls below by actually removing them and running the result.

Reference implementation

The reference implementation below always uses m = max(3, floor(sqrt(size))) buckets and a finishing threshold of 8 — both are implementation choices (Boost's real spreadsort() instead estimates the cheapest bit-width per level from a cost model), kept here because they're simple, reproducible, and are exactly what every measurement in Complexity and Pitfalls below actually ran:

function classOf(v, min, max, m) {
  if (max === min) return 0;
  let c = Math.floor((m - 1) * (v - min) / (max - min));
  if (c >= m) c = m - 1;              // v === max lands exactly on the last bucket
  return c;
}

function insertionSort(arr, lo, hi) {
  for (let i = lo + 1; i < hi; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= lo && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
    arr[j + 1] = key;
  }
}

const THRESHOLD = 8;

function sortRegion(arr, lo, hi) {
  const size = hi - lo;
  if (size <= 1) return;
  if (size <= THRESHOLD) { insertionSort(arr, lo, hi); return; }

  let min = arr[lo], max = arr[lo];               // scan THIS region only
  for (let i = lo + 1; i < hi; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }
  if (min === max) return;                        // every value here is identical

  const m = Math.max(3, Math.floor(Math.sqrt(size)));
  const counts = new Array(m).fill(0);
  for (let i = lo; i < hi; i++) counts[classOf(arr[i], min, max, m)]++;

  const starts = new Array(m), ends = new Array(m);
  let acc = lo;
  for (let c = 0; c < m; c++) { starts[c] = acc; acc += counts[c]; ends[c] = acc; }

  const next = starts.slice();                     // per-bucket write cursor
  for (let c = 0; c < m; c++) {
    while (next[c] < ends[c]) {
      const idx = next[c];
      const d = classOf(arr[idx], min, max, m);
      if (d === c) { next[c]++; continue; }
      [arr[idx], arr[next[d]]] = [arr[next[d]], arr[idx]];   // swap into its real bucket
      next[d]++;
    }
  }

  for (let c = 0; c < m; c++) sortRegion(arr, starts[c], ends[c]);   // recurse, bucket by bucket
}

function spreadSort(a) {
  const arr = a.slice();
  sortRegion(arr, 0, arr.length);
  return arr;
}

Correctness checked against 10,000 randomized trials (sizes 0–400, values ±1,000) plus 3,000 duplicate-heavy trials (values drawn from a 4-value range) — 0 mismatches against a reference sort in either set.

Pitfalls

Reusing the original array's global min/max instead of recomputing it per region defeats the entire point of recursing — it doesn't crash, it just silently regresses to the exact failure mode Spreadsort exists to fix. It's a tempting shortcut, since the value range never actually changes. But every child region's classification formula then spreads values across the original range instead of its own, narrower one — identical to reusing bucket sort's own formula unscaled, except recursively. Checked directly: on an array where 95% of 500 values are packed into a 20-wide band and the rest are spread across a range of 100,000 (the same construction bucket sort's and Flash Sort's own pitfalls sections use), the buggy version never finished 5,000 region-splits' worth of work in any of 5 trials — the clustered band keeps getting reclassified against the same wide global range, splitting into the same lopsided shape every level, forever. The correct version handles the same input in a double-digit number of region-splits (see Complexity).

Skipping the min === max base case causes genuine infinite recursion on any input with a large enough run of identical values — not a slowdown, a hang. Once every value left in a region is the same, classOf's own max === min guard returns bucket 0 for literally everything, so the "distribute" step places every element back into one bucket spanning the exact same [lo, hi) range it started with, and the size-based threshold check alone never catches it because the region's size never shrinks. Checked directly: 50 identical values (well above the finishing threshold) never terminated in 2,000 region-visits; a more realistic 195-identical-plus-5-random 200-element array hit the same wall just as fast, since the 195 duplicates dominate whichever bucket they land in. The one-line if (min === max) return; guard in the reference implementation above is load-bearing, not defensive boilerplate.

Complexity

Time (typical case), measured, not asserted: comparisons scale close to linearly with n on uniformly random data — 34 at n=20, 164 at n=100, 814 at n=500, 3,313 at n=2,000, 8,060 at n=5,000 (each 10-trial average), the same practical shape Flash Sort measured for the same reason: most of the ordering work happens in the classify-and-permute step, and the insertion-sort finish only ever runs on regions already narrowed to threshold size or smaller.

Where recursion actually pays for itself: on the clustered construction from Pitfalls above (95% of the array packed into a 20-wide band, the rest spread over a 100,000-wide range), a single-level classifier has no way out — it has to finish that one oversized bucket with a full comparison sort. Measured directly against that exact failure:

Comparisons (8-trial averages; the single-level column reuses the exact classify formula above, just without recursing). The gap widens with n because the single-level version's oversized bucket grows roughly with the array, paying O(n²) inside it, while recursion keeps re-narrowing that same cluster until it's small enough to finish cheaply.

Time (adversarial worst case), also measured directly — recursion narrows a clustered range, but it doesn't defeat every skew: feed it a range built so one value dominates the local max at every level (values doubling from 1: 1, 2, 4, 8, …, shuffled) and the classification formula squeezes nearly everything else toward bucket 0 relative to whichever value is currently the biggest — the same one-sided split repeats one level down, and the one dominant value peels off one region at a time instead of the range collapsing. Measured total per-region work (region size summed over every region visited, not just leaf comparisons) against uniform random data at the same sizes:

The doubling-values column roughly quadruples every time n doubles — consistent with an O(n²) trend, not the near-linear growth uniform data gets. Recursion fixes the specific failure mode above it (values clustered within an otherwise- wide range, because narrowing to the cluster's own bounds actually shrinks the problem); it does nothing for a range engineered so the dominant extreme keeps moving with it. Space: O(m) per active region for its own counts/starts/ends/cursor arrays, plus recursion depth — O(log n) typically, since a well-spread region roughly halves-or-better each level, but O(n) in the worst case above, where recursion depth tracks the number of values peeled off one at a time.

See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries.