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.
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.