Bucket Sort: Distribute, Sort Small, Concatenate
Bucket Sort spreads values into buckets by range, sorts each tiny bucket with insertion sort, then concatenates. Full JavaScript walkthrough and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most sorting algorithms you learn first are comparison sorts — they figure out order by asking "is A bigger than B?" over and over, and the best of them are stuck at O(n log n). Bucket Sort takes a different bet: if you already know roughly where a value belongs, you can drop it into the right neighborhood without comparing it to everyone else.
The move is simple. Split the value range into n buckets, scatter each element into the bucket its value maps to, sort each little bucket, and glue the buckets back together in order. When values are spread out evenly, each bucket ends up holding about one element, and the whole thing runs in linear time.
The catch — and the reason this pattern is worth understanding rather than memorizing — is that its speed depends entirely on the distribution of the input, not just its size.
The problem
Sort an array of non-negative integers into non-decreasing order using distribution rather than pure comparison. Concretely: given [7, 3, 9, 6, 2], return [2, 3, 6, 7, 9].
Input: arr = [7, 3, 9, 6, 2]
Output: [2, 3, 6, 7, 9]Bucket Sort assumes the values are numeric and reasonably spread across a known range — that's what lets you compute a bucket index directly from a value. It shines on uniformly distributed data (think normalized floats or evenly scattered integers) and degrades badly when everything clumps into one place, as we'll see in the complexity section.
The brute force baseline
The no-thinking-required approach is to run a single O(n²) comparison sort over the whole array. Insertion sort is the honest baseline here, because Bucket Sort actually reuses it internally:
function insertionSort(arr) {
for (let i = 1; i < arr.length; 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;
}On [7, 3, 9, 6, 2] this works fine, but every element potentially shifts past every element before it. For an array where each of the n insertions walks back through up to n slots, that's O(n²) total — quadratic. The problem is that insertion sort pays for distance: a small value near the end of the array has to be dragged all the way to the front, one swap at a time.
Bucket Sort's whole trick is to make sure that never happens — by ensuring no element ever has far to travel.
The key insight: sort by neighborhood, not by comparison
Here's the reframe. Instead of sorting all n elements together, first partition them so that every value lands in a bucket, and bucket k only ever holds values smaller than every value in bucket k+1. That's the invariant the whole algorithm rests on.
If that ordering-between-buckets holds, then sorting within each bucket and reading the buckets left to right gives you a globally sorted array — no merge step required, because the buckets are already in the right relative order.
To place a value, scale it into a bucket index:
idx = floor((value * n) / (max + 1))The * n / (max + 1) maps the value range [0, max] onto the bucket range [0, n-1]. The + 1 on max is deliberate: it keeps the largest element from computing an index of n (out of bounds) and instead lands it safely in the last bucket. With n buckets for n elements, a uniform input averages ~1 element per bucket, so each internal insertion sort is nearly free.
The optimal solution
This is the exact implementation the Bucket Sort visualizer steps through, insertion sort and all:
function bucketSort(arr) {
let n = arr.length;
let max = Math.max(...arr);
let buckets = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
let idx = Math.floor((arr[i] * n) / (max + 1));
buckets[idx].push(arr[i]);
}
for (let b = 0; b < n; b++) {
insertionSort(buckets[b]);
}
let out = [];
for (let b = 0; b < n; b++) {
for (let v of buckets[b]) {
out.push(v);
}
}
return out;
}
function insertionSort(bucket) {
for (let i = 1; i < bucket.length; i++) {
let key = bucket[i];
let j = i - 1;
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j];
j--;
}
bucket[j + 1] = key;
}
}Three distinct phases, each linear on its own: distribute (one pass placing every element), sort buckets (insertion sort on each small list), and concatenate (one pass emptying buckets in order). The insertion sort is chosen deliberately — it's the fastest option when the input is small and nearly sorted, which is exactly what each bucket is.
Walkthrough
Trace arr = [7, 3, 9, 6, 2]. Here n = 5, max = 9, so max + 1 = 10 and idx = floor(value * 5 / 10) = floor(value / 2).
Distribute — compute each index and drop the value in:
| Step | value | idx = floor(v·5/10) | Buckets after drop |
|---|---|---|---|
| 1 | 7 | 3 | b3=[7] |
| 2 | 3 | 1 | b1=[3], b3=[7] |
| 3 | 9 | 4 | b1=[3], b3=[7], b4=[9] |
| 4 | 6 | 3 | b1=[3], b3=[7,6], b4=[9] |
| 5 | 2 | 1 | b1=[3,2], b3=[7,6], b4=[9] |
After distribution the buckets are b0=[], b1=[3,2], b2=[], b3=[7,6], b4=[9]. Notice buckets 1 and 3 each caught two elements — and both landed out of order.
Sort each bucket — insertion sort fixes the local disorder:
| Bucket | Before | key inserted | Shift | After |
|---|---|---|---|---|
| b1 | [3, 2] | key = 2 | 3 > 2, shift 3 right | [2, 3] |
| b3 | [7, 6] | key = 6 | 7 > 6, shift 7 right | [6, 7] |
| b4 | [9] | — | none | [9] |
Concatenate — walk buckets 0→4, appending each in order:
| Bucket | Contributes | Output so far |
|---|---|---|
| b1 | [2, 3] | [2, 3] |
| b3 | [6, 7] | [2, 3, 6, 7] |
| b4 | [9] | [2, 3, 6, 7, 9] |
Because b1 < b3 < b4 by construction, concatenation alone produces the fully sorted [2, 3, 6, 7, 9]. No comparison between buckets was ever needed.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Insertion sort (whole array) | O(n²) | O(1) | each element can shift past all others |
| Bucket Sort — average (uniform input) | O(n + k) | O(n + k) | ~1 element per bucket, so per-bucket sort is O(1) |
| Bucket Sort — worst case | O(n²) | O(n) | every value collides into one bucket |
Here k is the number of buckets (n in this implementation), so the average case simplifies to O(n). The average holds only when the input is roughly uniform. The worst case is real: feed it [10, 10, 10, 10] — with max + 1 = 11, every value maps to floor(10·4/11) = 3, so bucket 3 holds all four elements and the internal insertion sort is back to O(n²). Space is O(n) regardless, for the buckets plus the output array.
Common mistakes
- Forgetting the
+ 1onmax. Without it, the maximum element computesidx = floor(max * n / max) = n, which is out of bounds and crashes. The+ 1guarantees every index stays in[0, n-1]. - Assuming Bucket Sort is always linear. It's O(n) on average for uniform data only. Skewed or clustered inputs collapse elements into few buckets and drag it back to O(n²).
- Sorting buckets with a heavy algorithm. Insertion sort is the right choice precisely because buckets are tiny and nearly sorted. Swapping in quicksort adds overhead that the small bucket sizes don't earn back.
- Using it on negative numbers as-is. The index formula assumes non-negative values. Negatives produce negative indices; you'd need to shift the range first.
- Expecting a merge step. Beginners sometimes try to merge buckets like in merge sort. The buckets are already globally ordered — plain concatenation is correct and cheaper.
Where this pattern shows up next
Distribution — placing elements by value instead of comparing them — powers a whole family of sub-O(n log n) sorts:
- Counting Sort — the purest distribution sort, using a value-indexed tally instead of buckets.
- Counting Sort - Stable - Logic — how a prefix-sum pass preserves the order of equal keys.
- Counting Sort - Stable - Code — the stable implementation line by line.
- Quick Sort — the comparison-based partitioning cousin, for when values aren't numeric or bounded.
You can also step through Bucket Sort interactively to watch values rain into their buckets, each bucket sort itself, and the output fill left to right.
FAQ
What is the time complexity of Bucket Sort?
On average, with uniformly distributed input, Bucket Sort runs in O(n + k) time, where k is the number of buckets — which simplifies to O(n) when you use n buckets. The worst case is O(n²), triggered when the input is skewed enough that most or all elements land in a single bucket and the internal insertion sort dominates. Space is O(n) for the buckets and output.
Why does Bucket Sort use insertion sort inside each bucket?
Because buckets are expected to be small and nearly sorted, and insertion sort is the fastest practical choice for exactly those conditions — it does almost no work when a list is already close to ordered. On a uniform input each bucket holds about one element, so each internal sort finishes in O(1). A heavier algorithm like quicksort would add setup overhead that the tiny bucket sizes never repay.
When should I use Bucket Sort instead of Quick Sort?
Use Bucket Sort when values are numeric and spread reasonably evenly across a known range, since that's when its linear average case kicks in — normalized floating-point data is the classic fit. Use Quick Sort (or another comparison sort) when values are arbitrary, unbounded, non-numeric, or clustered, because those inputs destroy Bucket Sort's distribution assumption and can push it to O(n²).
Why is there a + 1 added to max in the index formula?
The formula floor(value * n / (max + 1)) maps values into bucket indices 0 through n-1. Without the + 1, the largest element would compute floor(max * n / max) = n, an index one past the last bucket, causing an out-of-bounds error. Adding one to the denominator keeps that maximum value safely inside the final bucket.
Is Bucket Sort stable?
It can be, but only if the sort used inside each bucket is stable and elements are concatenated in bucket order. The insertion sort shown here is stable — it never moves an element past an equal one — so this implementation preserves the relative order of equal keys. Swapping in an unstable internal sort like quicksort would break that guarantee.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.