Algorithms in a Nutshell

Bucket Sort

Counting Sort succeeds by constructing a much smaller set of k values in which to count the n elements in the set. Given a set of n elements, Bucket Sort constructs a set of n buckets into which the elements of the input set are partitioned; Bucket Sort thus reduces its processing costs at the expense of this extra space. If a hash function, hash(A_i), is provided that uniformly partitions the input set of n elements into these n buckets, then Bucket Sort as described in Figure 4-18 can sort, in the worst case, in O(n) time. You can use Bucket Sort if the following two properties hold:

Uniform distribution

The input data must be uniformly distributed for a given range. Based on this distribution, n buckets are created to evenly partition the input range.

Ordered hash function

The buckets must be ordered. That is, if i<j, then elements inserted into bucket b_i are lexicographically smaller than elements in bucket b_j.

Figure 4-18. Bucket Sort fact sheet

Bucket Sort is not appropriate for sorting arbitrary strings, for example; however, it could be used to sort a set of uniformly distributed floating-point numbers in the range [0,1).

Once all elements to be sorted are inserted into the buckets, Bucket Sort extracts the values from left to right using Insertion Sort on the contents of each bucket. This orders the elements in each respective bucket as the values from the buckets ...