A distribution sort that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sort algorithm. It is a distribution sort, a generalization of pigeonhole sort that allows for a larger range of keys.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
{
"arr": "[0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]",
"n": 5
}Overview
Bucket Sort spreads values across a fixed number of buckets according to where they fall in the overall range, sorts each bucket individually, and concatenates the buckets. If values are spread evenly, each bucket holds only a few items and the whole sort runs in near-linear time.
This page's version uses 5 buckets and the index formula Math.floor(n * (x - min) / (max - min + 1)). Each bucket is sorted with the built-in sort, which is fine because buckets are expected to be small.
The default input is six decimals between 0.12 and 0.90. Because of the + 1 in the formula (which is meant for integers), every value lands in buckets 0–2 and buckets 3–4 stay empty. Watching the buckets variable in the dry run makes that uneven spread easy to see.
Step by step
- Find
minandmaxof the input. - Create
nempty buckets. - Put each value into bucket
floor(n * (x - min) / (max - min + 1)). - Sort each bucket (insertion sort or the built-in sort).
- Concatenate the buckets in order.
Complexity
| Case | Cost | Why |
|---|---|---|
| Best case | O(n + k) | Values spread evenly over k buckets, so each bucket is tiny. |
| Average case | O(n + k) | Holds for uniformly distributed input. |
| Worst case | O(n^2) | All values fall into one bucket and that bucket is sorted with a quadratic sort. |
| Extra space | O(n + k) | The buckets hold every element once. |
When to use it
- Floating-point values that are roughly uniformly distributed, e.g. random numbers in [0, 1).
- Data whose distribution you know, so you can size buckets to match it.
- Parallel sorting: buckets can be sorted independently on different threads.
Common mistakes
- Skewed data breaks the performance guarantee because most items pile into a few buckets.
- The
max - min + 1denominator is right for integers but compresses fractional ranges, as the default example shows; use(max - min)with a guard for the maximum value when sorting decimals. - Choosing too few buckets wastes the idea; too many wastes memory.
A dry run is the best way to check your understanding of Bucket Sort: follow each row, predict the next one, and compare. The run below takes 35 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434
- Result
- return value = [0.1234,0.3434,0.565,0.656,0.665,0.897]
| Step | Line | Array | What happens |
|---|---|---|---|
| 1 | 1 | [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434] | n = 5 |
| 34 | 16 | [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897] | result = [0.1234,0.3434,0.565,0.656,0.665,0.897] |
| 35 | 17 | [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897] | return value = [0.1234,0.3434,0.565,0.656,0.665,0.897] |