Bucket Sort and Radix Sort

Bucket sorts and radix sorts are efficient for sorting integers.
All sort algorithms discussed so far are general sorting algorithms that work for any types of keys (e.g., integers, strings, and any comparable objects). These algorithms sort the elements by comparing their keys. It has been proven that no sorting algorithms based on comparisons can perform better than O(n logn). However, if the keys are integers, you can use a bucket sort without having to compare the keys.

The bucket sort algorithm works as follows. Assume the keys are in the range from 0 to t. We need t + 1 buckets labeled 0, 1, . . . , and t. If an element’s key is i, the element is put into the bucket i. Each bucket holds the elements with the same key value.

You can use an ArrayList to implement a bucket. The bucket sort algorithm for sorting a list of elements can be described as follows:

void bucketSort(E[] list) {
E[] bucket = (E[])new java.util.ArrayList[t+1];
// Distribute the elements from list to buckets
for (int i = 0; i < list.length; i++) {
int key = list[i].getKey(); // Assume element has the getKey() method
if (bucket[key] == null)
bucket[key] = new java.util.ArrayList<>();
bucket[key].add(list[i]);
}
// Now move the elements from the buckets back to list
int k = 0; // k is an index for list
for (int i = 0; i < bucket.length; i++) {
if (bucket[i] != null) {
for (int j = 0; j < bucket[i].size(); j++)
list[k++] = bucket[i].get(j);
}
}
}

Clearly, it takes O(n + t) time to sort the list and uses O(n + t) space, where n is the list size.

Note that if t is too large, using the bucket sort is not desirable. Instead, you can use a radix sort. The radix sort is based on the bucket sort, but a radix sort uses only ten buckets.

It is worthwhile to note that a bucket sort is stable, meaning that if two elements in the original list have the same key value, their order is not changed in the sorted list. That is, if element e1 and element e2 have the same key and e1 precedes e2 in the original list, e1 still precedes e2 in the sorted list.

Assume that the keys are positive integers. The idea for the radix sort is to divide the keys into subgroups based on their radix positions. It applies a bucket sort repeatedly for the key values on radix positions, starting from the least-significant position.

Consider sorting the elements with the following keys:

331, 454, 230, 34, 343, 45, 59, 453, 345, 231, 9

Apply the bucket sort on the last radix position, and the elements are put into the buckets as follows:

After being removed from the buckets, the elements are in the following order:

230, 331, 231, 343, 453, 454, 34, 45, 345, 59, 9

Apply the bucket sort on the second-to-last radix position, and the elements are put into the buckets as follows:

After being removed from the buckets, the elements are in the following order:

9, 230, 331, 231, 34, 343, 45, 345, 453, 454, 59

(Note that 9 is 009.)

Apply the bucket sort on the third-to-last radix position, and the elements are put into the buckets as follows:

After being removed from the buckets, the elements are in the following order:

9, 34, 45, 59, 230, 231, 331, 343, 345, 453, 454

The elements are now sorted.

Radix sort takes O(dn) time to sort n elements with integer keys, where d is the maximum number of the radix positions among all keys.