Bucket sort is a distribution-based sorting algorithm. Instead of comparing elements, it spreads them into "buckets" based on their value, sorts each bucket individually, then concatenates the results. When data is uniformly distributed, it achieves average O(n) time — faster than comparison-based sorts which are bounded by O(n log n).

How Bucket Sort Works

1. Find the minimum and maximum values in the input
2. Create k empty buckets covering the value range
3. Distribute each element into its appropriate bucket
4. Sort each bucket individually
5. Concatenate all buckets in order to produce the sorted output

Visual Walkthrough

Input: [42, 13, 75, 29, 88, 5, 61, 37] — min=5, max=88, 4 buckets

Range per bucket = (88 - 5 + 1) / 4 ≈ 21

Bucket 0 [5–25]:   [13, 5]      → sorted: [5, 13]
Bucket 1 [26–46]:  [42, 29, 37] → sorted: [29, 37, 42]
Bucket 2 [47–67]:  [61]         → sorted: [61]
Bucket 3 [68–88]:  [75, 88]     → sorted: [75, 88]

Final result: [5, 13, 29, 37, 42, 61, 75, 88] ✓

Java Implementation

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

public class BucketSort {

    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int min = arr[0], max = arr[0];
        for (int val : arr) {
            if (val < min) min = val;
            if (val > max) max = val;
        }

        if (min == max) return; // all values are equal

        int bucketCount = arr.length;
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        double divisor = (double)(max - min + 1) / bucketCount;
        for (int val : arr) {
            int bucketIndex = (int)((val - min) / divisor);
            // Clamp to avoid floating-point edge cases
            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
            buckets.get(bucketIndex).add(val);
        }

        int index = 0;
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (int val : bucket) {
                arr[index++] = val;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {42, 13, 75, 29, 88, 5, 61, 37};

        System.out.print("Before: ");
        for (int v : data) System.out.print(v + " ");

        bucketSort(data);

        System.out.print("\nAfter:  ");
        for (int v : data) System.out.print(v + " ");
    }
}

Output:

Before: 42 13 75 29 88 5 61 37
After:  5 13 29 37 42 61 75 88

Floating-Point Variant

Bucket sort is classically defined for floating-point values in [0, 1):

public static void bucketSortFloat(double[] arr) {
    int n = arr.length;
    List<List<Double>> buckets = new ArrayList<>(n);
    for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());

    for (double val : arr) {
        int index = (int)(val * n);
        if (index == n) index = n - 1;
        buckets.get(index).add(val);
    }

    int pos = 0;
    for (List<Double> bucket : buckets) {
        Collections.sort(bucket);
        for (double val : bucket) arr[pos++] = val;
    }
}

// Usage:
double[] data = {0.72, 0.17, 0.39, 0.55, 0.14, 0.81};
bucketSortFloat(data);
// Result: 0.14 0.17 0.39 0.55 0.72 0.81

Time and Space Complexity

The worst case happens when input is highly skewed — all elements cluster in one bucket and the inner sort dominates.

When to Use Bucket Sort

Good fit:

• Input values are uniformly distributed across a known finite range
• Sorting floating-point numbers between 0 and 1
• You need average O(n) performance and can afford O(n + k) extra memory

Poor fit:

• Input is skewed (bucket sort degrades to O(n²))
• The value range is unknown or extremely large
• Memory is constrained
• You need a guaranteed worst-case bound — use merge sort instead

Bucket Sort vs. Other Algorithms

For production use, Java's Arrays.sort() uses dual-pivot quicksort for primitives and Timsort for objects — both highly optimized. Implement bucket sort when you have a measured bottleneck and know your data distribution is uniform.