Bucket Sort: Coarse Positions Need Local Sorting

A bucket gives each value a coarse position, not its final position

Bucket sort divides the value range into ordered bucket ranges, then sends each value to the range that contains it. For the array [29, 25, 3, 49, 9, 37, 21, 43], five width-10 buckets cover 0-9, 10-19, 20-29, 30-39, and 40-49. A value in a lower range must appear before every value in a higher range, so the bucket gives that value a correct coarse position.

After the distribution scan, the buckets are [3, 9], [], [29, 25, 21], [37], and [49, 43]. Reading the buckets from the lowest range to the highest gives the right large-scale order, but bucket 20-29 still contains 29 before 25 before 21. Those values belong in the same region, yet their internal order is wrong.

One index formula must place every value in exactly one bucket

For this fixed value range, the bucket index is the integer division index = value / 10. Integer division discards the remainder, so values 0 through 9 produce index 0, values 10 through 19 produce index 1, and so on. With five buckets numbered 0 through 4, this formula maps every allowed value from 0 through 49 to one valid bucket.

value     value / 10     bucket range
9         0              0-9
29        2              20-29
49        4              40-49

The boundary values show why the division rule works: 9 stays in bucket 0, 29 goes to bucket 2, and 49 goes to bucket 4. Each value gets one index because the ranges do not overlap, and no value in 0-49 falls between the ranges.

Only sorted buckets produce a sorted concatenation

Sort the contents of each bucket before collecting them. Bucket 0 changes from [3, 9] to [3, 9], bucket 1 stays empty, bucket 2 changes from [29, 25, 21] to [21, 25, 29], bucket 3 stays [37], and bucket 4 changes from [49, 43] to [43, 49]. The local sorting step fixes the order that the bucket index formula cannot determine.

Now collect the buckets in increasing bucket index order. Every value in bucket 0 is less than every value in bucket 1, every value in bucket 1 is less than every value in bucket 2, and the same relation continues through bucket 4. Because each bucket is also internally sorted, the collected array is [3, 9, 21, 25, 29, 37, 43, 49]. Global order requires both parts: ordered buckets between ranges and sorted values within each range.

Bucket sort is fast only when the values spread across the buckets

The work has three separate pieces for this array. The distribution scan reads all eight values and places each into a bucket, which takes O(n). The local sorting step sorts the contents of each bucket, with its cost determined by the bucket sizes and the inner sorting algorithm. The collection step visits all five buckets and writes their eight values, which takes O(n + k), where k is the number of buckets.

If bucket i contains m_i values and insertion sort is used inside every bucket, the total time is O(n + k + sum(m_i^2)). The sum describes the local work rather than pretending every bucket has the same size. For this array, the bucket sizes are 2, 0, 3, 1, and 2, so the local work stays small because no bucket is crowded.

When values spread across many buckets, the buckets remain small and the running time can be near O(n + k). If all eight values enter one bucket, that bucket must handle all eight values internally, and insertion sort can take O(n^2) work. The extra storage is O(n + k), because the buckets hold all n values and there are k bucket containers.