Bucket Sort

Bucket Sort is a sorting algorithm that works by dividing the input list into buckets. Each bucket is then individually sorted using another sorting algorithm , and finally the buckets are merged back together. The operations are as follows:

1. Create buckets each of which is a list.
2. For each element in the input list, hash it to determine which bucket it belongs to.
3. Sort each of the buckets using .
4. Merge all the sorted buckets back together.

The most important property of Bucket Sort is that it assumes a uniform distribution of the input list. If the input list is uniformly distributed, then each bucket will be of equal size. If the elements are not uniformly distributed, then the size of the buckets will vary, and the performance of the sort will degrade.

Picking is a trade-off between the computation time and memory space required to sort the input list. The more buckets we allocate, the more memory space we require, but we might be able to sort the input using fewer comparisons. In fact, in the best scenario, we can sort the input list without any comparisons at all ().

Time complexity analysis

Depending on the amount of buckets we allocate for the input list, the behavior of the algorithm will be different. We can picture the following scenarios:

1. There are the same number of buckets as elements in the input list ()
2. There are fewer buckets than elements in the input list ()

If the number of buckets is equal to the number of elements, then zero comparisons are required. This is because the hashing function will position each element into the correct bucket based on its value. This is the best scenario, and in this case, the expected time complexity is expressed as .

If we have fewer buckets than we do elements, then each bucket will have some element count greater than one. This means that the sub-sorting procedure will require at least one comparison against the other elements within the same bucket. This time, the time complexity depends on the sorting algorithm used to sort the buckets. If we express the time complexity of as , then the total time complexity of Bucket Sort is .

This aligns with our first scenario. The time required to sort a bucket of size is , because the bucket is already sorted.

A third scenario is when the number of buckets is greater than the number of elements, but this is rarely ever the case in practice. In the case where there are more buckets than elements, we’re simply sorting empty lists during the merge phase. This has zero implication on the time complexity of the algorithm. As we will see, this will, however, have a negative impact on the space complexity.

Space complexity analysis

As we saw in the time complexity analysis, the space complexity of Bucket Sort depends on the number of buckets we allocate. Good implementations will use a data structure that doesn’t perform unnecessary allocations, such as a linked list. This is because we don’t know how many elements will be in each bucket in advance. Using a linked list means we only ever allocate nodes across the buckets. This means that the space complexity of Bucket Sort is .

If we were to pre-allocate the buckets, then we would have to allocate elements in each bucket unless we choose a data structure that is capable of resizing. In this scenario, the space complexity of Bucket Sort is .

Implementation

The following is a Java implementation of the Bucket Sort algorithm. In order to simplify the implementation, we use the standard Collections.sort method to sort the individual buckets. Depending on the Java JDK version, and the data type provided, the implementation is typically either TimSort, MergeSort, or a Dual-Pivot Quicksort.

Java Implementation

package jun.codes.interviews.sort;

import java.util.Collections;
import java.util.LinkedList;

public class BucketSort {
  public static <T extends Comparable<T>> void sort(T[] xs, int k) {
    // While BucketSort assumes a uniform distribution, we cannot guarantee that
    // the collection is uniform. Therefore, the worst case scenario is that
    // all elements of `xs` go into the same bucket.
    LinkedList<T>[] buckets = (LinkedList<T>[]) new LinkedList[k];
    for (int i = 0; i < k; i++) {
      buckets[i] = new LinkedList<>();
    }

    // To get the ideally uniform position in the array, we need to find the
    // minimum and maximum values
    T min = xs[0];
    T max = xs[0];
    for (T x : xs) {
      if (x.compareTo(min) < 0) {
        min = x;
      }
      if (x.compareTo(max) > 0) {
        max = x;
      }
    }

    // Insert each element into its corresponding bucket
    for (T x : xs) {
      double range = max.compareTo(min);
      double norm = x.compareTo(min) / range;
      int bucket = (int) (norm * (k - 1));
      buckets[bucket].add(x);
    }

    // Merge all the buckets into the original array
    int i = 0;
    for (LinkedList<T> bucket : buckets) {
      Collections.sort(bucket);
      for (T x : bucket) {
        xs[i] = x;
        i++;
      }
    }
  }
}

Further reading

The relevant material in Introduction to Algorithms 4th edition can be found starting on page 215.

• Wikipedia: Bucket Sort