How to Implement the Bucket Sort Algorithm

Introduction

Bucket Sort is a non-comparative sorting technique that performs best when the input elements are evenly spread across a specific range. The core strategy involves dividing the data into multiple containers called “buckets,” sorting the contents of each bucket, and then combining the results to form the sorted list. This method is especially efficient for sorting floating-point numbers that fall within a known interval, such as values between 0 and 1.

Step-by-Step Process

1. Choose how many buckets to create based on the input size and distribution.
2. Assign each element from the input array to the correct bucket depending on its value.
3. Sort the contents of each bucket, often using a simple sorting algorithm like Insertion Sort.
4. Concatenate the sorted buckets to produce the final sorted array.

Performance Analysis

• Best Case: O(n + k), where k is the number of buckets used
• Average Case: O(n + k)
• Worst Case: O(n²), which can happen if all values end up in a single bucket

Java Implementation of Bucket Sort

	@Test
	public void ShellSortTest() throws Exception {
        float[] input = {0.23f, 0.15f, 0.78f, 0.91f, 0.45f, 0.39f};
        bucketSort(input);
		for (float elem : input) {
			System.out.println(elem + " ");
		}
	}

    private void bucketSort(float[] arr) {
        if (arr.length <= 0)
            return;

        int n = arr.length;
        ArrayList<Float>[] buckets = new ArrayList[n];

        for (int i = 0; i < n; i++)
            buckets[i] = new ArrayList<>();

        for (float value : arr) {
            int index = (int)(value * n);
            buckets[index].add(value);
        }

        for (ArrayList<Float> bucket : buckets)
            Collections.sort(bucket);

        int index = 0;
        for (ArrayList<Float> bucket : buckets) {
            for (float value : bucket) {
                arr[index++] = value;
            }
        }
    }

Explanation of the Code

The bucketSort method first creates an array of empty buckets. Each input number is then placed into a bucket based on its value. Since the numbers are assumed to be in the range [0, 1), multiplying each value by the number of buckets gives a suitable index. After all numbers are distributed, each bucket is individually sorted using Java’s built-in Collections.sort(). Finally, the sorted buckets are concatenated to reconstruct the full sorted array.

Conclusion

Bucket Sort can be extremely fast when dealing with inputs that are uniformly distributed, especially floating-point numbers. Although it’s not suitable for all data types or distributions, it can outperform more general-purpose algorithms like quicksort under the right conditions.

You can find the example code on Github.