Bucket Sort Algorithm

What is Bucket Sort?

Bucket Sort (also known as bin sort) is a non-comparison-based sorting algorithm that distributes elements into a number of buckets, sorts each bucket individually (usually using another algorithm like Insertion Sort), and then concatenates the results to form the final sorted array.

It is particularly useful when:

• Input is uniformly distributed over a known range.
• You want to achieve linear time sorting in practical cases.

How Bucket Sort Works

1. Create buckets to hold ranges of values.
2. Distribute input elements into these buckets based on their value.
3. Sort each bucket individually using a simple sort (e.g., Insertion Sort).
4. Concatenate all sorted buckets back into the original array.

Characteristics of Bucket Sort

• Efficient for real numbers (floating points) in a known range, typically [0, 1).
• Stable, depending on the inner sorting algorithm.
• Often faster than comparison sorts when inputs are evenly distributed.

When to Use Bucket Sort

• Data is evenly or uniformly distributed.
• Elements are in a known, limited range (e.g., 0 to 1).
• Performance needs to be better than O(n log n) in real-world cases.

Time & Space Complexity

• n = number of elements
• k = number of buckets
• Space Complexity: O(n + k)

Code Example

import java.util.*;

public class BucketSortExample {

    public static void bucketSort(float[] arr) {
        int n = arr.length;
        if (n <= 0) return;

        // Step 1: Create empty buckets
        @SuppressWarnings("unchecked")
        List<Float>[] buckets = new List[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // Step 2: Distribute elements into buckets
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int)(arr[i] * n);
            buckets[bucketIndex].add(arr[i]);
        }

        // Step 3: Sort each bucket
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets[i]); // could use Insertion Sort
        }

        // Step 4: Concatenate all buckets into arr[]
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (float value : buckets[i]) {
                arr[index++] = value;
            }
        }
    }

    public static void printArray(float[] arr) {
        for (float value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f, 0.47f, 0.51f};
        System.out.println("Original array:");
        printArray(arr);

        bucketSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output

Original array:
0.42 0.32 0.33 0.52 0.37 0.47 0.51 
Sorted array:
0.32 0.33 0.37 0.42 0.47 0.51 0.52 

Bucket Sort – Visual Explanation (Step-by-Step)

Given array:

[0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]

Step 1: Create Buckets

Create 7 buckets (same as array length):

buckets[0], buckets[1], ..., buckets[6]

Step 2: Distribute into Buckets

Calculate bucket index using:
index = (int)(value * n)

• 0.42 → index 2
• 0.32 → index 2
• 0.33 → index 2
• 0.52 → index 3
• 0.37 → index 2
• 0.47 → index 3
• 0.51 → index 3

Buckets:

buckets[2] → [0.42, 0.32, 0.33, 0.37]  
buckets[3] → [0.52, 0.47, 0.51]

Step 3: Sort Each Bucket

Sort values inside each bucket:

• buckets[2] → [0.32, 0.33, 0.37, 0.42]
• buckets[3] → [0.47, 0.51, 0.52]

Step 4: Concatenate Buckets

Final sorted array:

[0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

Summary

• Bucket Sort distributes elements into groups (buckets), sorts each group, and then joins them.
• Efficient for floating-point numbers in a known range like [0, 1).
• Time complexity is linear in the best case, but depends on the distribution of input.