Bucket sort
Bucket sort divides the range from the smallest to the largest value into a fixed number of buckets, reads each value in turn and drops it into the bucket covering its range, sorts each bucket that ends up holding more than one item, then writes the buckets back into the array in order. Unlike counting sort, a bucket can hold many different values, so each one needs its own small sort rather than a simple count.
When it is the right choice
Bucket sort is a good choice when values are spread roughly evenly across a known range and a plain array cannot cheaply hold one slot per distinct value the way counting sort does. It degrades toward its O(n²) worst case when the values are badly clustered, since most of them then land in one bucket and that bucket's own sort dominates; on data like that, a comparison sort with a guaranteed O(n log n) bound is the safer choice.
How it works
- Find the smallest and largest value in the array and divide that range evenly into a fixed number of buckets.
- Read each value in turn and place it into the bucket whose range covers it.
- Sort each bucket that ends up holding more than one item — this implementation uses insertion sort, since buckets are usually small.
- Walk through the buckets in order, writing each one's sorted contents back into the array.
Worth noticing
- This implementation always uses ten buckets, however many items there are or however wide their range — unlike counting sort, its aux track never has to grow with the value range, at the cost of buckets that can hold more than one distinct value and so need a real sort.
- With a narrow value range, such as the small-values preset, each bucket ends up covering a single value, and the trace becomes indistinguishable from counting sort: distribute into ten single-value buckets, then drain them in order. That is the concrete sense in which counting sort is bucket sort with single-value buckets, and radix sort is bucket sort applied once per digit.
- Its worst case is quadratic, not linear: if every value lands in the same bucket, that bucket's insertion sort does the same O(n²) work a plain insertion sort would on the whole array.
- The aux track only shows how many items each bucket currently holds, not which values are in it or their order — the per-bucket sort happens out of view, and only the running count changes.
Cost
- Best
- O(n + k)
- Average
- O(n + k)
- Worst
- O(n²)
- Extra space
- O(n + k)
- Stable
- Yes