↩ back to Non-Comparison Sorts
Counting sort needs small integer keys, and
radix sort extends that to wide integers by working one
digit at a time. Neither helps if the keys are real numbers spread continuously over a range —
there's no "next digit" to peel off, and no integer bucket to index by value directly. Bucket sort
handles this case, but it makes a different assumption than either of its neighbors on this site: not
that the keys are small integers, but that they're roughly uniformly distributed
over a known range. Scale each value into one of k buckets, drop it in, then finish each
bucket — usually small — with a plain insertion sort.
If the uniformity assumption holds, most buckets end up with only a handful of elements each and the
whole thing runs in expected linear time. If it doesn't, see Pitfalls.
Enter a comma-separated list of real numbers, each in [0, 1) (this demo caps it at 16
values). Step through three phases: distributing each value into bucket
floor(value × k) — this demo always uses k equal to the array length,
the classic choice — sorting each bucket independently with insertion sort, then
collecting the buckets in order, 0 through k−1, into the output.
Buckets are drawn as chained rows, the same shape as this site's hash
table demo — which is not a coincidence, see Why it works.
Three passes. First, distribute: walk the input once, and for each value
v compute floor(v × k) — since every value is in [0, 1),
this always lands in [0, k) — and append it to that bucket's chain. This is arithmetic,
not comparison, the same trick counting sort's indexing uses, just scaled instead of offset. Second,
sort each bucket: run insertion sort on every bucket's contents independently. This
part is not comparison-free — it's the one place in this technique that still pays the
Ω(n log n) comparison-sort tax counting sort and radix sort both fully dodge. What
bucket sort buys instead is making sure each individual sort is cheap: if the values really are
uniformly spread over [0, 1) and there are k = n buckets, the expected
number of values landing in any one bucket is O(1) (a balls-into-bins argument — n
balls into n bins, uniformly and independently, average bin load 1). Insertion sort on a
constant-expected-size list costs constant expected time, and summing that over k buckets
gives O(n) expected total — so the technique doesn't defeat the comparison-sort lower
bound in the worst case, it just usually keeps every individual comparison sort's input so small that
the bound is nearly free. Third, collect: walk the buckets in index order and
concatenate their (now-sorted) contents — correct because bucket i only ever holds values
in [i/k, (i+1)/k), so every value in bucket i is less than every value in
bucket i+1 by construction, no matter what order the buckets are visited in during
distribution.
The bucket layout itself — an array of chains, each one a variable-length list of values that
landed in the same slot — is the exact same shape as separate-chaining collision resolution in this
site's own hash table. That's not a
surface-level resemblance: floor(v × k) is a hash function, uniform input is
exactly the assumption a good hash function's output should satisfy, and "most chains stay short so
each one is cheap to scan" is the identical argument that gives a hash table its expected
O(1) lookup — the same argument that breaks down the same way, too, when
hash table's own Pitfalls section describes a
bad hash function clustering keys into a few long chains instead of spreading them evenly.
Assumes every input value is in [0, 1); a general range [min, max) just
needs the same affine rescale counting sort's negative-value offset uses. This is the exact scheme the
demo above steps through:
function bucketSort(arr) {
const n = arr.length;
if (n === 0) return [];
const k = n; // one bucket per element
const buckets = Array.from({ length: k }, () => []);
for (const v of arr) { // distribute
let b = Math.floor(v * k);
if (b >= k) b = k - 1; // guard v === 1 exactly
buckets[b].push(v);
}
for (const bucket of buckets) insertionSort(bucket); // sort each bucket
return buckets.flat(); // collect, in bucket order
}
function insertionSort(a) {
for (let i = 1; i < a.length; i++) {
const cur = a[i];
let j = i - 1;
while (j >= 0 && a[j] > cur) { a[j + 1] = a[j]; j--; }
a[j + 1] = cur;
}
return a;
}The whole technique depends on the values actually being spread out. Nothing
about the algorithm checks this — it just runs the same three passes regardless, and the cost falls
entirely on whichever bucket the input happens to concentrate in. A quick, real check on
n = 200 values, k = 200 buckets, insertion-sort comparisons counted
directly and cross-checked against a plain Array.prototype.sort for correctness both
times: uniformly random values over [0, 1) spread across every bucket, the largest
holding just 5 elements, for 90 total insertion-sort comparisons. The same 200 values, but all drawn
from the narrow range [0.50, 0.51) instead of the full [0, 1), collapse
into just 2 of the 200 buckets — one holding 107 elements — for
5,235 comparisons, roughly 58× more work sorting the exact same number of
values. Nothing crashes and the output is still correctly sorted either way; the algorithm degrades to
plain insertion sort on whichever bucket absorbed everything, silently, with no warning that the
uniformity assumption it was relying on didn't hold. In the true worst case — every value landing in
one bucket — this is O(n²), no better than starting with insertion sort directly,
plus the extra O(n+k) distribution overhead on top for nothing.
Choosing k requires knowing the value range in advance. This demo
fixes the range at [0, 1) so floor(v × k) always lands in bounds; a
real dataset needs its min and max known or estimated first, the same
prerequisite counting sort's bucket array has. Too few buckets crowds values together for the same
reason a skewed distribution does — the fix above doesn't require adversarial input, just an
under-provisioned k. Too many buckets wastes memory on buckets that stay empty, mirroring
counting sort's own k-vs-n tradeoff exactly, just measured in bucket count
instead of key-range width.
This is a hybrid, not a pure non-comparison sort. Distribution is arithmetic, like
counting sort and radix sort. But the per-bucket insertion sort is a real comparison sort, and its
Ω(n log n) worst case (per bucket, on a skewed input, potentially the whole array)
is never dodged — only usually avoided, when the buckets stay small. Swapping insertion sort for a
faster comparison sort inside each bucket doesn't change this; it only changes the constant, since the
lower bound applies to any comparison-based sort regardless of which one is chosen.
Time: O(n+k) expected when values are uniformly distributed and
k is chosen proportional to n (this demo always sets k = n,
giving expected O(n)) — one pass to distribute (O(n)), expected
O(1) per bucket to sort (O(n) total across k buckets), one pass
to collect (O(n)). Worst case O(n²) when the distribution collapses
most values into one bucket, exactly the first Pitfall above, measured for real rather than just
asserted. Space: O(n+k) — the bucket chains hold every input element
once (O(n)) plus the bucket array itself (O(k)), on top of the input, unlike
heap sort's O(1) in-place swaps.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries — short version: this is the one built for continuous, roughly uniform keys, not integers.