Bucket Sort: Spreading Keys Into Ranges, Then Sorting Each Range

When keys are spread evenly, each bucket holds a handful of items and the whole sort is close to linear.

Bucket sort is a sorting algorithm for keys spread across a known range: it splits the range into equal intervals called buckets, drops each item into the bucket its key falls in, sorts each bucket with a simple sort, and joins the buckets in order. This card covers the steps, the bucket index, and why the sort is fast only when the keys are spread evenly.

The bucket for a key comes from its position in the range. With b buckets over the range from low to high, a key's bucket is (key − low) × b ÷ width, rounded down, where the width is the number of values the range holds. Every key in bucket 0 is smaller than every key in bucket 1, so once each bucket is sorted, joining the buckets from first to last gives the sorted array. Each bucket is usually sorted with insertion sort, which is fast on a few items.

The table sorts 13 4 10 7 14 3 10 with five buckets over the range 0 to 14, so each bucket covers three values and a key's bucket is the key divided by 3, rounded down.

Five buckets of width 3 for the keys 13 4 10 7 14 3 10
Bucket	Range	Items	Sorted items
0	0 to 2	none	none
1	3 to 5	4 3	3 4
2	6 to 8	7	7
3	9 to 11	10 10	10 10
4	12 to 14	13 14	13 14

Read the Sorted items column from top to bottom and it is the output, 3 4 7 10 10 13 14. No bucket held more than two items, so sorting them cost almost nothing. That is the case bucket sort is built for, and the reason it needs an assumption. A run sorted 1,000 numbers between 0 and 1 into 1,000 buckets twice. With the numbers spread evenly, the fullest bucket held 6 and the insertion sorts made 466 comparisons in all. With every number below 1/1000, all of them landed in bucket 0, and the one insertion sort made 243,781 comparisons, about half of n(n − 1)/2 = 499,500, which is what insertion sort costs on items in random order.

Sorting a pile of exam papers by first dividing them into trays for A to E, F to J, and so on, then sorting each tray by hand, is a bucket sort. The analogy breaks on how surnames are spread: far more of them begin with S than with X, so the trays fill unevenly, and a real bucket sort would choose its ranges from how the keys are spread rather than from the alphabet.

Bucket sort on n keys with b buckets

Best and average case: O(n + b); keys spread evenly, with b about n, so each bucket holds O(1) items
Worst case: O(n²); every key in one bucket, sorted by insertion sort
Extra space: O(n + b); b buckets holding n items between them
Stable: Yes; if the sort inside each bucket is stable, as insertion sort is
In place: No; the items are copied into the buckets

The sign to reach for bucket sort is keys you know to be spread evenly over a known range: readings from a uniform random source, hash values, fractions between 0 and 1. Keys that cluster, such as response times that are mostly short with a long tail, put most items in a few buckets, and the sort slides towards its quadratic worst case.

On the Algorithms: Efficient Sorting cheatsheet

← → move through sections and cards