Java Bucket Sort for Uniformly Distributed Data

Introduction

Bucket sort java developers use it when they need to sort uniformly distributed floating point or integer keys in expected linear time. The algorithm was first described by Harold Seward in 1954 in his MIT master's thesis, where he generalised counting sort to handle a continuous key space by partitioning it into discrete buckets. The algorithm was further analysed by Donald Knuth in The Art of Computer Programming Volume 3 (1973), who proved that bucket sort achieves expected O(n) time when the input keys are drawn from a uniform distribution over the unit interval.

For a Java learner, bucket sort java demonstrates how a distribution assumption can collapse the O(n log n) comparison lower bound into expected linear time. By scattering keys into buckets, sorting each bucket with a comparison sort, and gathering the buckets in order, the algorithm sorts in expected O(n plus k) time where k is the bucket count. Building bucket sort from scratch teaches the link between distribution shape, hash function quality, and load balancing, which appears again in hash tables, partitioned databases, and the reduce side of map reduce.

What is Bucket Sort?

Bucket sort is a distribution sort that partitions the input into k buckets based on key value, sorts each bucket individually, and concatenates the buckets in order. It belongs to the distribution sort family alongside counting sort and radix sort. Unlike counting sort, which requires integer keys in a small range, bucket sort handles floating point keys by mapping each key to a bucket index through a hash function. The expected linear time guarantee depends on the keys being approximately uniformly distributed across the buckets.

If the keys are uniform, each bucket receives O(n / k) items, and sorting each bucket with a comparison sort takes O((n / k) log (n / k)) time. Across k buckets, the total sorting cost is O(n log (n / k)). For k proportional to n, this collapses to O(n). If the keys are not uniform, the worst case is one bucket receiving all n items, and the sort degrades to O(n log n).

Bucket sort is stable if and only if the underlying per bucket sort is stable. Using insertion sort per bucket, which is stable and fast on small inputs, gives a stable bucket sort. Using quick sort per bucket gives an unstable bucket sort.

How Bucket Sort Works - Step by Step

Step 1: Choose the bucket count. For n input items, a common choice is k equals n, so each bucket receives an expected one item. For floating point keys in the range 0 to 1, the bucket index for a key x is floor(k times x), which distributes uniform keys evenly.

Step 2: Create the bucket array. Allocate an array of k empty lists. Each list will hold the items that hash to that bucket index.

Step 3: Scatter the input into buckets. For each input item, compute its bucket index and append the item to the corresponding bucket. After this pass, each bucket contains the items whose keys hash to its index.

Step 4: Sort each bucket individually. Use a stable comparison sort such as insertion sort on each non empty bucket. Insertion sort is fast on small inputs and preserves stability. The expected bucket size is O(1) when k equals n, so each per bucket sort runs in expected O(1) time.

Step 5: Gather the buckets in order. Walk the bucket array from index 0 to k minus 1, and for each non empty bucket, append its sorted items to the output. The output is now fully sorted.

Java Program for Bucket Sort

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BucketSortDemo {

    // Sorts an array of doubles in the range [0, 1) using bucket sort.
    // Assumes uniform distribution for expected O(n) running time.
    public static void bucketSort(double[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        int n = arr.length;

        // Step 1: create n buckets, one per input item.
        List<List<Double>> buckets = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            buckets.add(new ArrayList<>());
        }

        // Step 2: scatter each input item into its bucket.
        // bucketIndex = floor(n * key) since keys are in [0, 1).
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (n * arr[i]);
            // Guard against key exactly equal to 1.0 (which would
            // give bucketIndex = n, out of range).
            if (bucketIndex >= n) {
                bucketIndex = n - 1;
            }
            buckets.get(bucketIndex).add(arr[i]);
        }

        // Step 3: sort each bucket individually.
        // Collections.sort is stable, so bucket sort is stable.
        for (int i = 0; i < n; i++) {
            if (!buckets.get(i).isEmpty()) {
                Collections.sort(buckets.get(i));
            }
        }

        // Step 4: gather the buckets back into the input array.
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (double value : buckets.get(i)) {
                arr[index++] = value;
            }
        }
    }

    public static void main(String[] args) {
        double[] data = {0.42, 0.32, 0.87, 0.05, 0.50, 0.21, 0.73, 0.91, 0.18};

        System.out.print("Input:  ");
        for (double v : data) {
            System.out.print(v + " ");
        }
        System.out.println();

        bucketSort(data);

        System.out.print("Output: ");
        for (double v : data) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

Code Explanation - Line by Line

The method starts with a defensive check for null or empty input and returns immediately. This avoids allocating a 0 sized bucket array and avoids index out of bounds on the gather loop.

The bucket list is created with n slots, one per input item. Each slot holds an ArrayList of Double objects. Using ArrayList gives O(1) amortised append, which is essential because we do not know the size of each bucket in advance.

The scatter loop walks the input and computes the bucket index as floor(n times key). For a key of 0.42 with n equals 9, the bucket index is floor(3.78) equals 3. The guard checks if the bucket index exceeds n minus 1, which can happen if a key equals 1.0 or slightly exceeds 1.0 due to floating point error. Clamping to n minus 1 keeps the algorithm safe.

The per bucket sort uses Collections.sort, which runs a stable merge sort on List inputs. Stable means items with the same key appear in the same order in the output as they appeared in the input, which propagates through the gather loop and gives a stable bucket sort. An empty bucket is skipped to avoid unnecessary work.

The gather loop walks the bucket array in order and copies each non empty bucket's contents into the original array. The index variable tracks the next free slot in the input array. After the loop, the input array is fully sorted.

Sample Input and Output

Input:  0.42 0.32 0.87 0.05 0.50 0.21 0.73 0.91 0.18
Output: 0.05 0.18 0.21 0.32 0.42 0.50 0.73 0.87 0.91

The output is the sorted input. Each item was placed in the bucket floor(9 times key), which distributes the 9 items across 9 buckets. With a uniform distribution, the expected bucket size is 1, so the per bucket sort cost is negligible. The total work is dominated by the scatter and gather passes, each O(n), giving an overall expected O(n) running time.

Common Mistakes to Avoid

First, do not assume the keys are uniform. Bucket sort achieves expected O(n) only when keys are uniformly distributed across the bucket range. If the keys cluster, some buckets receive many items and the per bucket sort cost explodes. Always check the distribution before relying on the linear time guarantee.

Second, do not forget to guard the bucket index against out of range values. A key exactly equal to the upper bound (1.0 in our example) gives bucket index n, which is out of range. Either clamp the index to n minus 1 or use a half open interval convention that excludes the upper bound.

Third, do not use an unstable per bucket sort if you need overall stability. Quicksort per bucket is faster in the worst case but loses the original relative order of equal keys. Use insertion sort or merge sort per bucket if stability matters.

Fourth, do not choose k much smaller than n. If k is constant, the per bucket sort cost is O(n log n) and bucket sort reduces to a comparison sort in disguise. The linear time guarantee requires k proportional to n.

Real-World Applications

Bucket sort is used in the reduce side of Hadoop and Spark map reduce pipelines, where intermediate keys are partitioned across reducers using a hash function. The partition step is essentially a scatter into buckets, and the per reducer sort handles the in bucket ordering. The choice of partition function determines the load balance across reducers.

In graphics rendering, bucket sort is used to sort triangles by depth (z value) for the painter's algorithm. Because depth values are bounded and roughly uniform in many scenes, bucket sort gives near linear time depth sorting, which is critical for real time rendering.

In database engines, bucket sort is used to sort floating point columns when the row count is large and the column distribution is known to be uniform. The optimiser chooses bucket sort over merge sort when the bucket count can be tuned to match the available memory and the distribution is favourable.

In competitive programming, bucket sort is the standard trick for problems that ask to sort n floating point keys in O(n) time, given a uniform distribution guarantee. It also appears in closest pair of points algorithms, where points are bucketed by coordinate to enable O(1) neighbour scans.

Conclusion

We built bucket sort from scratch and saw how scattering keys into k buckets, sorting each bucket, and gathering the buckets produces an expected O(n) sort for uniform keys. We learned that the distribution assumption is essential, that stability propagates from the per bucket sort, and that the bucket count must scale with n. Next, study shell sort, which uses a different kind of bucketing with shrinking gaps, and comb sort, which is bubble sort with a shrinking gap between compared items.