Bucket sort
mediumSplits by value rather than by position, so concatenating the buckets needs no merge step. Load the 'few unique' preset to watch every value land in one bucket and the whole thing degenerate.
O(n + b)Average O(n + n²/b + b)Worst O(n²)Space O(n + b)StableNeeds extra memorySaved in this browser - no sign-up, nothing sent anywhere.
How bucket sort works
Split the value range - not the array - into b equal slices, and scatter each element into its slice's bucket with one multiplication: floor(b × x / (max + 1)). Every value in bucket i is smaller than every value in bucket i + 1, so after insertion-sorting each bucket individually, plain concatenation produces the sorted array. No merge step exists because the scatter already did the coarse ordering.
The speed is a bet on uniformity. If n values spread evenly across b buckets, each holds about n/b elements, and insertion sort on tiny buckets is nearly free - the average works out to O(n + n²/b + b), effectively linear when b is proportional to n. The 16 default values here land 2 to 4 per bucket across 5 buckets, exactly the spread the bet assumes.
Skewed data loses the bet: load the few-unique preset and every copy of a value maps to the same bucket, collapsing the run into one big O(n²) insertion sort. Compare its niche with its relatives - counting sort needs small integer ranges, radix needs digit structure - bucket sort is the one for continuous keys like uniform floats, where slicing the range is natural. As built here it is stable: the scatter preserves scan order and insertion sort keeps it.
Step by step
- Sort 16 values with maximum 93 into 5 buckets - each bucket covers about 19 values: 0..18, 19..37, 38..56, 57..75, 76..93.
- Scatter with one multiply each: 42 maps to bucket 2, 17 to bucket 0, 93 to bucket 4. Bucket 0 collects [17, 8, 5, 12].
- After 16 placements the bucket sizes are 4, 3, 4, 3, 2 - the roughly even spread the algorithm bets on.
- Insertion-sort each bucket: bucket 0 becomes [5, 8, 12, 17], bucket 2 becomes [38, 42, 49, 55], and so on.
- Concatenate buckets 0 through 4 - no merging, because everything in bucket 1 (19..37) is below everything in bucket 2 (38..56).
- Rerun with the few-unique preset: the duplicates pile into shared buckets and the run degenerates toward one large quadratic insertion sort.
Complexity
| Best case time | O(n + b) |
|---|---|
| Average time | O(n + n²/b + b) |
| Worst case time | O(n²) |
| Space | O(n + b) |
Assumes values are roughly uniform; skewed data collapses into one bucket.
Reference implementation
Python
def bucket_sort(a, b=5):
if not a:
return a
hi = max(a) + 1
buckets = [[] for _ in range(b)]
for x in a:
buckets[b * x // hi].append(x)
out = []
for bucket in buckets:
bucket.sort() # any sort; insertion is typical
out.extend(bucket)
return outJavaScript
function bucketSort(a, b = 5) {
if (!a.length) return a;
const hi = Math.max(...a) + 1;
const buckets = Array.from({ length: b }, () => []);
for (const x of a) buckets[Math.floor((b * x) / hi)].push(x);
return buckets.flatMap((bucket) => bucket.sort((p, q) => p - q));
}Worth noticing
It is only fast if the data spreads out
Bucket sort assumes values are roughly uniform. Load the 'few unique' preset and watch every value land in one bucket: the whole thing degenerates to a single insertion sort, O(n²).
Divide by value, not by position
Unlike merge sort, which splits the array in half by index, bucket sort splits by value range. That is why concatenating the buckets needs no merge step - bucket i is entirely less than bucket i+1.
Common pitfalls
- Dividing by max instead of max + 1 in the bucket formula - the maximum element computes bucket index b, one past the last bucket. This implementation clamps with min(b - 1, ...) as a second guard.
- Assuming the input is uniform. Clustered or skewed data funnels into few buckets, and the worst case is one bucket holding everything - O(n²), no warning.
- Over-provisioning buckets: with far more buckets than elements, the O(b) cost of creating and scanning empties dominates the sort itself.
- Porting the integer formula to floats carelessly. The max + 1 trick assumes integers; for floats, scale by the actual range and clamp the top edge explicitly.
- Swapping the per-bucket insertion sort for an unstable one when stability matters - the concatenation preserves whatever the buckets produce, including their mistakes.
Where it is used
- The textbook linear-average sort for uniform floats in [0, 1) - random samples, normalized scores, hash fractions.
- Graphics and simulation: binning sprite depths or particle coordinates that spread evenly over a known range.
- Distributed sorting: scatter records into value ranges across machines, sort shards independently, concatenate - TeraSort is bucket sort at datacenter scale.
- The interview analysis exercise: derive O(n + n²/b + b) and say exactly when the uniformity assumption fails.
Frequently asked questions
What is the time and space complexity of bucket sort?
Best case O(n + b) when every bucket stays tiny; average O(n + n²/b + b), which is effectively linear when values are uniform and b is proportional to n; worst case O(n²) when everything lands in one bucket. Space is O(n + b) for the buckets, so it is not in place.
What is the difference between bucket sort and counting sort?
Counting sort keeps one counter per exact value and never sorts anything - it needs a small integer range. Bucket sort keeps one list per slice of the value range and runs a real sort inside each, so it handles floats and wide ranges - but its speed depends on the data spreading evenly, which counting sort never worries about.
What is the difference between bucket sort and radix sort?
Radix sort makes d passes, one per digit, is stable by construction, and its cost is independent of how values are distributed. Bucket sort makes one scatter by overall value and gambles on uniformity - faster when the bet pays, quadratic when it does not - and it extends naturally to continuous keys that have no digits to peel.
When is bucket sort O(n)?
When the keys are roughly uniformly distributed and the bucket count grows with n. Then each bucket holds a constant number of elements on average, the per-bucket insertion sorts sum to O(n), and the scatter and concatenation are single passes. Break the uniformity and the n²/b term in the average takes over.