Bucket Sort

By Victor Arce

Counting sort needs one bin per value, and radix sort fakes that with one bin per digit. Bucket sort takes a different bet: if the values are spread fairly evenly over a range, you can split that range into a handful of buckets, drop each value into the bucket its range covers, sort each bucket on its own, and then read the buckets back in order. The buckets are coarse, so each one still holds a mix of values — which is why bucket sort, unlike counting and radix, sorts inside each bucket before gathering.

Step through it below with values 0–99 split into five buckets of width 20. Scatter each value into its bucket, sort each bucket, then gather the buckets left to right. Toggle show log to follow along.

How it works

1. Scatter. Walk the input; each value v goes into bucket ⌊v / width⌋ — here width = 20, so 0–19 lands in the first bucket, 20–39 in the next, and so on.
2. Sort each bucket. A bucket holds a range of different values, not equal keys, so it isn't sorted yet. Sort each one with a simple sort (insertion sort is the classic choice — buckets are expected to be small).
3. Gather. Concatenate the buckets in order 0, 1, …. Because the buckets partition the range and each is internally sorted, the result comes out sorted.

The whole gamble is the distribution. If the values spread evenly, each bucket holds about n / k items and the per-bucket sorts are tiny. If they all clump into one bucket, bucket sort degrades to whatever sort runs inside that bucket.

Cost

With n items spread over k buckets, scattering and gathering are O(n + k), and the per-bucket sorts cost O(n²/k) in total with insertion sort. When the input is uniformly distributed and k ≈ n, that average works out to O(n)O(n) — linear time: the work grows in direct proportion to the number of items n. — linear, like counting and radix. The worst case is O(n²)O(n²) — quadratic time: the work grows with the square of the number of items.: every value falls in one bucket and the inner sort does all the work. So bucket sort shines exactly when you know the data is evenly spread; for arbitrary integers, radix sort is the safer linear-time choice.

Back to Sorting Algorithms