Don't memorize bucket sort — watch values fall into place. Split the range into k ordered buckets, drop each value into the one that covers it, sort each small bucket with a cheap insertion sort, then just read the buckets left to right. Because bucket 0 holds the lowest range and bucket k−1 the highest, the concatenation is already sorted — no merge. On evenly spread data it runs in O(n + k).
distribute · sort each bucket · concatenate · O(n + k) average
DISTRIBUTE
Drop value v into bucket ⌊v / width⌋ — grouped by value, not by comparison.
ORDERED BUCKETS
k contiguous ranges. Every value in bucket i is below every value in bucket i+1.
SORT EACH
Each bucket is small, so a simple insertion sort orders it cheaply.
CONCATENATE
Read the buckets in order — the result is sorted with no merge step.
bucket.sim — 10 values in [0, 99] → 5 buckets of width 20
Ready
Top is the unsorted input; below are 5 empty buckets, one per value range. Press Step: each value drops into its bucket, every bucket sorts itself, then reading left to right gives a sorted array.
bucket(v) = ⌊v / 20⌋ (clamped to k−1)
Input
Stage
0
Sorted out
Let the value pick the slot
Comparison sorts ask questions — is a before b? Bucket sort skips the questions and uses the value itself as an address. Divide the known range into k equal buckets, then send each value straight to bucket ⌊(v − min) / width⌋. That single arithmetic step does most of the ordering for free, because the buckets are laid out in increasing order. Whatever mess sits inside a bucket is tiny — on uniform data about n/k elements — so a plain insertion sort tidies it instantly. Then you gather: walk the buckets left to right and append. No comparisons across buckets, no merge, just concatenation of already-ordered ranges.
01
Scatter by value
index = ⌊(v − min) / width⌋. Each value lands in the bucket covering its range.
02
Order across buckets is free
Bucket i only holds values below bucket i+1, so between-bucket order is already correct.
03
Sort within each bucket
Buckets are small (≈ n/k), so insertion sort orders each one in near-constant time.
04
Gather in order
Concatenate the buckets left to right. The output is fully sorted — no merge.
Time (avg)
O(n + k)
Worst
O(n²)
Space
O(n + k)
Stable
Yes*
The catch is in the assumption: bucket sort is fast only when the values spread uniformly across the range. Cluster them all into one bucket and that bucket holds nearly n items, so the inner insertion sort costs O(n²) and you have gained nothing. When that assumption holds, though, it beats the O(n log n) comparison barrier — the same family as counting sort (exact integer tallies) and radix sort (digit by digit). It is stable as long as the per-bucket sort is stable and you append in arrival order.
The picture: where each value lands
Ten values in [0, 99], five buckets of width 20. The fullest bucket (20–39, highlighted) holds 4 values, and its own sort costs 6 comparisons; between buckets nothing is compared at all.
Worked example, step by step
Take [78, 17, 39, 26, 72, 94, 21, 12, 23, 68] with k = 5 buckets over [0, 99], so each bucket spans 20 values. Scatter left to right; each row shows the buckets after that value arrives, in arrival order.
The scatter used no comparisons between values at all. Now each bucket is sorted by insertion sort: the sizes are [2, 4, 0, 3, 1], and the five sorts together cost 10 comparisons (bucket 1, the fullest, accounts for 6 of them). Gathering gives [12, 17, 21, 23, 26, 39, 68, 72, 78, 94]. For scale, merge sort on the same ten values would make up to about 33 comparisons. The trace also shows the shape of the risk: bucket 2 stayed empty while bucket 1 took four values. Nothing broke, but the work is the sum of the squares of the bucket sizes, so a lopsided scatter is exactly where the time goes.
Complexity and trade-offs
Case
Time
Space
Why
Bucket sort, uniform data
O(n + k) average
O(n + k)
Scatter is one pass; buckets hold about n/k values. Measured on 1,000 uniform floats with k = n: 446 insertion-sort comparisons in total, largest bucket 5.
Bucket sort, one crowded bucket
O(n²) with insertion sort
O(n + k)
The same 1,000 values squeezed into [0.5, 0.500001): they all land in one bucket (size 1000) and cost 250416 comparisons.
Bucket sort, merge sort per bucket
O(n log n) worst
O(n + k)
Caps the crowded case at the comparison-sort bound, at the price of a heavier inner loop on the common case.
Merge sort / quicksort
O(n log n)
O(n) / O(log n)
Needs no assumption about the data. Merge sort made 8687 comparisons on the same uniform 1,000 floats.
Counting sort / radix sort
O(n + range) / O(d · (n + b))
O(n + range)
Integer keys only, but no worst-case collapse: the key range, not the data distribution, sets the cost.
Bucket sort trades a guarantee for a distribution assumption. On uniform data it does 446 comparisons against 8687 for merge sort, a gap of about 19.5×, and it parallelises naturally because buckets are independent. The costs are an extra O(n + k) of memory, a need to know the value range up front, and the cliff in the crowded case. Choosing k near n keeps buckets about one element long; a much smaller k pushes the work back into the inner sort.
Common mistakes
Ignoring the minimum
The index ⌊v / width⌋ only works for values starting at 0. With [-5, 30, 50], Python computes -5 // 20 = -1, which silently indexes the last bucket, so the output is [30, 50, -5] instead of [-5, 30, 50]. Use ⌊(v − min) / width⌋.
Letting the maximum overflow
With [0, 100], five buckets of width 20 and the formula v // 20, the value 100 maps to bucket 5, which does not exist (IndexError). Clamp with min(k − 1, …) or size the width as (max − min + 1) / k.
Trusting the distribution
On [1, 2, 3, 4, 5, 6, 7, 8, 9, 1000] with five buckets over the observed range, the sizes come out as [9, 0, 0, 0, 1]: nine values share one bucket. The algorithm is still correct, but the inner insertion sort is now doing nearly all of the work. Check bucket sizes if the data might be skewed, or fall back to a comparison sort.
Gathering buckets in the wrong order
Storing buckets in a map and iterating it gives them in first-arrival order, not range order. On the page-style input [78, 17, 39, 26, 72, 94, 21, 12, 23, 68], a dict keyed by bucket index visits bucket 3 first and yields [68, 72, 78, 12, 17, 21, 23, 26, 39, 94]. Always loop i = 0 … k − 1.
Breaking stability by prepending
Inserting at the front of a bucket reverses equal keys. Sorting records [[0.31, 'a'], [0.35, 'b'], [0.31, 'c']] with n buckets and prepending gives [[0.31, 'c'], [0.31, 'a'], [0.35, 'b']]: the two 0.31 records swap places. Append on arrival and use a stable inner sort.
Where this shows up
Uniformly distributed keys
Hashes, random numbers and normalised scores are close to uniform, which is the case bucket sort is built for. Sorting a large batch of floats in [0, 1) is the textbook use.
Histograms and percentiles
Counting how many values fall in each range is the scatter step on its own. A histogram, an approximate percentile sketch and a frequency table are all a bucket sort that stops before the gather.
Range partitioning before a big sort
Parallel and distributed sorts often split data by key range first so each worker sorts one range independently, then concatenate the results. That is bucket sort with the inner sort handed to a machine; the splitters are usually sampled so the buckets stay balanced.
Radix sort inside
LSD radix sort is a repeated, stable bucket distribution on one digit at a time. Understanding why bucket order carries the sorted order is the same idea that makes radix sort work.
SOLVE IT YOURSELF
Solve it: bucket sort
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement bucket_sort(nums) for floats in [0, 1): scatter each value into one of n buckets by ⌊x·n⌋, sort each small bucket (insertion sort), then concatenate the buckets in order. On uniform data this is O(n) on average.
HINTS — 4 IDEAS
With n values, make n empty buckets. Value x goes to bucket min(n−1, ⌊x·n⌋).
Because bucket i only holds values below bucket i+1, the buckets are already in order relative to each other.
Sort each bucket internally — insertion sort is perfect since each bucket is tiny.
Concatenate the buckets left to right. No merge needed — the result is fully sorted. Handle empty input by returning an empty list.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · Why is concatenating the buckets already a sorted array?
Buckets are contiguous ordered ranges, so once each is internally sorted, reading left to right visits values in non-decreasing order — no merge needed.
2 · When does bucket sort degrade to O(n²)?
Non-uniform input can pile ~n values into a single bucket; sorting that one bucket with insertion sort is O(n²), which dominates.
3 · What does bucket sort assume about its input?
Uniform distribution keeps each bucket small (≈ n/k), which is exactly what makes the average O(n + k) hold.
Questions
Bucket sort vs counting sort vs radix sort?
All three are non-comparison distribution sorts. Counting sort tallies exact counts of integer keys from a small range. Radix sort makes one stable pass per digit. Bucket sort groups wider or real-valued keys into ranges and sorts within each bucket — best when the input is uniformly spread over a known interval.
Is bucket sort stable?
Yes, if the sort used inside each bucket is stable (insertion sort is) and you append values to a bucket in their original order. Then equal keys keep their relative order in the final concatenation.
How many buckets should I use?
A common choice is k = n, so each bucket holds about one element on average and the inner sorts are trivial — giving the O(n) average. Fewer buckets means bigger, slower inner sorts; more buckets means more empty overhead.
The value is the address.
Scatter by range, sort each little bucket, read left to right — sorted in linear time when the data plays fair.