Bucket Sort
Scatter values into range-based buckets, sort each tiny bucket, and concatenate — linear time when data spreads evenly.
Hands on Interactive visualization
Implementation Code
export function bucketSort(a: number[]): number[] {
const n = a.length;
if (n < 2) return a;
const lo = Math.min(...a);
const hi = Math.max(...a);
if (lo === hi) return a; // all keys equal: nothing to do
const span = hi - lo + 1;
// k = n buckets: expected one element per bucket on uniform data.
const buckets: number[][] = Array.from({ length: n }, () => []);
for (const v of a) {
const idx = Math.floor(((v - lo) * n) / span); // hi -> last bucket
buckets[idx].push(v);
}
let pos = 0;
for (const b of buckets) {
// Insertion sort per bucket: tiny, and keeps the sort stable.
for (let k = 1; k < b.length; k++) {
const key = b[k];
let j = k - 1;
while (j >= 0 && b[j] > key) {
b[j + 1] = b[j];
j--;
}
b[j + 1] = key;
}
for (const v of b) a[pos++] = v; // concatenate in bucket order
}
return a;
}Big-O Complexity
k = bucket count. Average case assumes roughly uniform key distribution; skewed data can pile everything into one bucket, degrading to the inner sort's worst case.
In production When to use
The textbook case: sorting floats uniformly distributed in [0, 1) — random samples, normalized scores, probabilities — in expected linear time.
The scatter phase is exactly how distributed sorts shard work: range-partition keys across nodes (buckets), sort locally, concatenate. TeraSort-style benchmarks are bucket sort at cluster scale.
Depth binning: dropping renderables into a fixed array of depth slices approximates a sort in O(n) per frame, with exact sorting only inside each slice if needed.
Histogram-based range partitioning in query engines and index builds is bucket sort's scatter step: cheap statistics pick bucket boundaries so partitions come out balanced.
Bucketing values by range (latency histograms, percentile sketches) gives approximately ordered data with O(1) placement per element — often good enough without the final per-bucket sort.
Trade-offs Strengths & weaknesses
- Expected O(n) on uniformly distributed keys — with k ≈ n, buckets average one element each.
- Naturally parallel and distributable: buckets are independent by construction.
- Works on floats and any key with a cheap value-to-bucket mapping — unlike counting sort's integer requirement.
- Stable when the scatter preserves order and the inner sort is stable (e.g. insertion sort).
- Bucket boundaries can encode domain knowledge (histograms, quantiles) for balanced work.
- Distribution-sensitive: skewed data lands in one bucket and performance collapses to O(n²) with an insertion-sort inner loop.
- O(n + k) extra memory for buckets plus scattered allocation churn.
- Choosing bucket count and boundaries well requires knowing the data's range and shape.
- Poor cache locality during scatter: writes hop across k growing lists.
- Not adaptive, not online, and useless when the key range is unknown up front.
Intuition Mental model
Sorting mail into carrier routes
A mailroom does not compare every letter to every other letter. It throws each letter into the tray for its neighborhood, then each carrier orders their own small tray.
- Set out one tray per neighborhood (bucket per key range).
- Toss every letter into its tray by address — a single O(1) decision per letter, no comparisons across trays.
- Each carrier sorts their own tray; with even neighborhoods, each tray is tiny and quick.
- Concatenate trays in route order — the whole mailbag is now sorted.
- If one neighborhood gets all the mail (skew), that carrier does nearly all the original work alone — the O(n²) failure mode.
Prep Interview questions
When is bucket sort O(n), and what assumption does the proof lean on?
Bucket sort vs counting sort — what exactly is the difference?
How do you defend bucket sort against skewed distributions?
Why is insertion sort the usual inner sort rather than quicksort?
How does distributed sorting (e.g. TeraSort) relate to bucket sort?
Watch out Common bugs
A naive index formula sends v == max to bucket k, which does not exist. Clamp the index to k - 1 or derive the formula so the top value lands inside the last bucket.
(v - lo) * k can overflow fixed-width integers for wide ranges, producing negative indices. Widen the intermediate type or divide first.
The scatter preserves input order within each bucket; sorting buckets with an unstable algorithm throws that away. Use insertion sort (or another stable sort) if callers rely on stability.
max == min makes the bucket-width computation divide by zero. Detect the single-value case and return early.
One screen Cheat sheet
Scatter by range into k buckets, insertion-sort each bucket, concatenate.
- Expected linear only under (roughly) uniform key distribution.
- k ≈ n buckets targets one element per bucket on average.
- Skew is the killer: one hot bucket degrades to the inner sort's worst case.
- Stable if scatter order is preserved and the inner sort is stable.
- The blueprint for distributed range-partitioned sorting.
- Data-derived boundaries (quantiles) are the practical skew defense.