Bucket Sort: ranges first, order inside each range — Read

Opening the reading…

A bucket index identifies a value range, not a final positionThe running example uses six buckets for values in [0, 1).

The input contract for this example is that every value x satisfies 0 <= x < 1. With n = 6 buckets numbered 0 through 5, the bucket index is floor(6*x). This index tells you which range contains x, but it does not tell you the value's final position in the sorted array.

TEXTDistribution of the running-example values.

value   floor(6*x)   bucket
0.42    floor(2.52)   2
0.32    floor(1.92)   1
0.73    floor(4.38)   4
0.25    floor(1.50)   1
0.39    floor(2.34)   2
0.47    floor(2.82)   2

The values 0.42, 0.39, and 0.47 all enter bucket 2. They belong to the same value range, from 2/6 up to 3/6, but their insertion order is still 0.42, 0.39, 0.47. A bucket collision does not sort those values. Treating the bucket number as a final position would leave this group out of order.

CHECKPOINT 1Not answered

Using index = floor(6*x), where do 0.42, 0.39, and 0.47 go, and is that shared bucket already sorted?

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

Sorting each bucket makes left-to-right concatenation globally sortedBucket order handles different ranges, while local sorting handles collisions.

After distribution, the six buckets contain the values in their original insertion order: bucket 0 is empty, bucket 1 contains [0.32, 0.25], bucket 2 contains [0.42, 0.39, 0.47], bucket 3 is empty, bucket 4 contains [0.73], and bucket 5 is empty. The first pass has grouped values by range, but it has not finished sorting them.

BUCKET	BEFORE LOCAL SORTING	AFTER LOCAL SORTING
0	[]	[]
1	[0.32, 0.25]	[0.25, 0.32]
2	[0.42, 0.39, 0.47]	[0.39, 0.42, 0.47]
3	[]	[]
4	[0.73]	[0.73]
5	[]	[]

Each nonempty bucket is sorted before output is built.

Now read the sorted buckets from bucket 0 through bucket 5 and append their contents. Every value in an earlier bucket is no greater than every value in a later bucket, because the bucket ranges do not overlap. The local sort supplies the missing order within each bucket, so concatenation produces [0.25, 0.32, 0.39, 0.42, 0.47, 0.73].

DIAGRAM — NOT DRAWN YET

The input [0.42, 0.32, 0.73, 0.25, 0.39, 0.47] is distributed using index = floor(6*x). Buckets 0, 3, and 5 are empty. Bucket 1 initially contains [0.32, 0.25] and is sorted to [0.25, 0.32]. Bucket 2 initially contains [0.42, 0.39, 0.47] and is sorted to [0.39, 0.42, 0.47]. Bucket 4 contains [0.73]. Reading buckets 0 through 5 produces [0.25, 0.32, 0.39, 0.42, 0.47, 0.73].

Bucket order handles ranges, while local sorting handles order inside each range.

Bucket sort is fast only when no bucket becomes too crowdedThe local sort can dominate the work.

Distribution visits the n values once, and concatenation visits the buckets and their stored values. Those costs are O(n + k), where k is the number of buckets. The extra cost comes from sorting each bucket. For the running example, the bucket sizes are [0, 2, 3, 0, 1, 0].

If the local sorter takes quadratic time for a bucket of size m, its work is proportional to m squared. Across all buckets, the local work is proportional to the sum of the squared bucket sizes. For [0, 2, 3, 0, 1, 0], that sum is 0 squared + 2 squared + 3 squared + 0 squared + 1 squared + 0 squared = 14.

When values are suitably spread out, bucket sizes stay small and the expected total time is O(n + k). If many values crowd into one bucket, that bucket can contain almost all n values, making the worst-case time O(n squared + k). Storing n values across k buckets uses O(n + k) extra space.

CHECKPOINT 2Not answered

For bucket sizes [0, 2, 3, 0, 1, 0], type the largest bucket size and the sum of squared bucket sizes.

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

The value-to-bucket formula is part of the algorithm's contractThe formula is valid only for the promised input range.

For every running-example value, 0 <= x < 1, so floor(6*x) produces an index from 0 through 5. For example, 0.73 produces floor(4.38), which is 4. This range guarantee is what makes six buckets sufficient and keeps every computed index valid.

An implementation must preserve the same formula and its range assumptions. If x were exactly 1, floor(6*x) would be 6, which is outside bucket numbers 0 through 5. A negative value could produce a negative index. The algorithm must reject, transform, or separately handle values outside [0, 1) instead of silently applying this formula to them.