Idea: Distribute elements into buckets

• Average: O(n)
• Worst: O(n²)
• Depends on distribution

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

public class BucketSort {
    // Assumes values in [0, 1)
    public static void sort(double[] a) {
        int n = a.length;
        if (n == 0) return;

        List<List<Double>> buckets = new ArrayList<>(n);
        for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());

        for (double v : a) {
            if (v < 0.0 || v >= 1.0) {
                throw new IllegalArgumentException("BucketSort here expects values in [0, 1).");
            }
            int idx = (int) (v * n);
            buckets.get(idx).add(v);
        }

        for (List<Double> b : buckets) Collections.sort(b);

        int k = 0;
        for (List<Double> b : buckets) {
            for (double v : b) a[k++] = v;
        }
    }
}

Watch for

• Distribution into buckets
• Sorting inside buckets

Mental model: 🪣 Scatter → sort → gather