Bucket Sort

Sorting O(n + k) O(n + k)

Scatters values into a few range buckets, sorts each bucket, then concatenates them back — fast when the data spreads evenly.

Idle

Starting Bucket Sort on 8 elements (5 buckets).

InvariantEach bucket holds only values from its own range, so concatenating sorted buckets gives a sorted array.

1/31

comparisons0moves0probes0max0size0b0i0

compareswapshiftselectsorted

bucket-sort.c

#define BUCKETS 5
 
void bucketSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
 
    int bucket[BUCKETS][100], count[BUCKETS] = {0};
    int size = max / BUCKETS + 1;
 
    for (int i = 0; i < n; i++) {
        int b = arr[i] / size;
        bucket[b][count[b]++] = arr[i];
    }
 
    for (int b = 0; b < BUCKETS; b++)
        insertionSort(bucket[b], count[b]);
 
    int idx = 0;
    for (int b = 0; b < BUCKETS; b++)
        for (int j = 0; j < count[b]; j++)
            arr[idx++] = bucket[b][j];
}

How Bucket Sort works

Split the value range into a few buckets, scatter elements into them, sort each small bucket (insertion sort), then concatenate the buckets in order.

Best case

Uniformly spread data — buckets stay small: about O(n + k).

Worst case

All values land in one bucket — degenerates to that bucket's sort: O(n²).

When to use it

Data known to spread evenly over a range (e.g. uniform floats in [0,1)).