Bucket sort

Bucket sort assumes the input values are drawn roughly uniformly from a known range, such as real numbers in [0, 1) or integers in [0, 100). Under that assumption each of n buckets receives about one element.

If the assumption fails and most values land in a few buckets, the buckets become the bottleneck and the algorithm is only as fast as the algorithm used inside the buckets.

For n values in [0, 100) use n buckets and the index x * n / 100. For doubles in [0, 1) use (int) (x * n). The index is computed directly from the value, with no comparisons between elements.

Append each element to its bucket in input order. Use a linked list or ArrayList for each bucket. The animation labels each bucket with the range of values it covers.

1static void bucketSort(double[] a) {                    // values in [0, 1)
2    int n = a.length;
3    List<List<Double>> buckets = new ArrayList<>();
4    for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
5    for (double x : a) buckets.get((int) (x * n)).add(x);
6    for (List<Double> b : buckets) Collections.sort(b);
7    int k = 0;
8    for (List<Double> b : buckets)
9        for (double x : b) a[k++] = x;
10}

1public static void bucketSort(int[] arr) {                 // values in [0, 100)
2    int n = arr.length;
3    List<List<Integer>> buckets = new ArrayList<>();
4    for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
5    for (int x : arr) buckets.get(x * n / 100).add(x);
6    for (List<Integer> b : buckets) Collections.sort(b);
7    int k = 0;
8    for (List<Integer> b : buckets)
9        for (int x : b) arr[k++] = x;
10}

Each bucket is sorted separately. Insertion sort is the traditional choice, because buckets are small and insertion sort has almost no overhead on a handful of elements. Collections.sort also works, and it is stable.

Stability of the whole algorithm follows from two things: elements enter each bucket in input order, and the sort inside the bucket is stable.

Distributing costs O(n), concatenating costs O(n + number of buckets), and sorting the buckets costs the sum of cost(bucket size). For uniform data the expected bucket size is constant, so the expected total is O(n + k) with k buckets.

In the worst case every element falls into one bucket, which costs the inner sort on n elements: O(n²) with insertion sort, or O(n log n) with a merge-based sort. Compare the “Even spacing (ideal)” preset with “Clustered (worst case)” and read the size of the fullest bucket.