Bucket Sort Implementation

Problem Statement

Sort an array using bucket sort: distribute the elements into several buckets by value range, sort each bucket, then concatenate the buckets in order.

Example

Input:  [0.42, 0.32, 0.23, 0.52, 0.25, 0.47]
Bucketed by range -> sort each -> concat
Output: [0.23, 0.25, 0.32, 0.42, 0.47, 0.52]

Approach

Choose n buckets spanning the value range. Map each element to a bucket by its relative position, sort the (small) buckets individually, then read them out left to right. When the data is spread evenly, each bucket holds O(1) elements and the whole sort is O(n) on average.

Complexity

• Time: O(n + k) average (uniform data), O(n^2) worst
• Space: O(n)

Solution Code

Python

def bucket_sort(arr):
    if not arr:
        return arr
    n = len(arr)
    lo, hi = min(arr), max(arr)
    span = (hi - lo) or 1
    buckets = [[] for _ in range(n)]
    for x in arr:
        idx = int((x - lo) / span * (n - 1))
        buckets[idx].append(x)
    result = []
    for b in buckets:
        b.sort()
        result.extend(b)
    for i in range(n):
        arr[i] = result[i]
    return arr

Java

void bucketSort(double[] arr) {
    int n = arr.length;
    if (n == 0) return;
    List<List<Double>> buckets = new ArrayList<>();
    for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
    for (double x : arr) {
        int idx = Math.min(n - 1, (int)(x * n));   // assumes x in [0,1)
        buckets.get(idx).add(x);
    }
    int k = 0;
    for (List<Double> b : buckets) {
        Collections.sort(b);
        for (double v : b) arr[k++] = v;
    }
}

C++

void bucketSort(vector<double>& arr) {
    int n = arr.size();
    if (n == 0) return;
    vector<vector<double>> buckets(n);
    for (double x : arr) {
        int idx = min(n - 1, (int)(x * n));        // assumes x in [0,1)
        buckets[idx].push_back(x);
    }
    int k = 0;
    for (auto& b : buckets) {
        sort(b.begin(), b.end());
        for (double v : b) arr[k++] = v;
    }
}

Key Takeaways

• Bucket sort shines when data is uniformly distributed.
• Skewed data piles into one bucket and degrades to O(n^2).
• Reference: CLRS, Ch. 8; Wikipedia, "Bucket sort".