Bucket sort

Bucket sort is a distribution-based sorting algorithm: distribute the input into a number of “buckets” by some property of the value, sort each bucket individually (often with insertion sort), then concatenate. Unlike comparison-based sorts, bucket sort doesn’t directly compare elements — it relies on knowing something about the range of values being sorted.

Useful when input is uniformly distributed over a known range. Achieves $O (n + k)$ in the best case where $k$ is the number of buckets.

Algorithm

Choose bucket count $k$ , partition the value range into $k$ intervals.
Distribute: for each input element, compute which bucket it belongs to and add it.
Sort each bucket: usually with insertion sort, since each bucket should be small.
Concatenate: walk the buckets in order, listing their (now sorted) contents.

int getBucketIndex(int value) {
    int INTERVAL = 5;        // bucket size
    return value / INTERVAL;
}
 
void BucketSort(int arr[]) {
    struct Node *buckets[NBUCKET];
    
    for (int i = 0; i < NBUCKET; i++) {
        buckets[i] = NULL;
    }
    
    // distribute
    for (int i = 0; i < NARRAY; i++) {
        int pos = getBucketIndex(arr[i]);
        struct Node *current = malloc(sizeof(struct Node));
        current->data = arr[i];
        current->next = buckets[pos];
        buckets[pos] = current;
    }
    
    // sort each bucket
    for (int i = 0; i < NBUCKET; i++) {
        buckets[i] = InsertionSort(buckets[i]);
    }
    
    // concatenate back to arr
    int j = 0;
    for (int i = 0; i < NBUCKET; i++) {
        struct Node *node = buckets[i];
        while (node != NULL) {
            arr[j++] = node->data;
            node = node->next;
        }
    }
}

Big O

Best case: $O (n + k)$ — when elements distribute evenly across buckets, each bucket has $\approx n / k$ elements, sortable in $O (1)$ if $n / k$ is small.
Average case: $O (n + k)$ — same idea, depending on uniformity.
Worst case: $O (n^{2})$ — all elements end up in one bucket; that bucket’s insertion sort is $O (n^{2})$ .

So bucket sort is not a comparison sort and isn’t bound by the $Ω (n lo g n)$ lower bound. It can run in linear time when its assumptions hold — uniform distribution.

A practical caveat: the asymptotic $O (n)$ assumes constant-time bucket creation and insertion. If buckets are linked lists allocated one malloc per bucket and $k \approx n$ , you pay $n$ allocator calls, each often much more expensive than a simple array index. The “linear time” then hides $n$ malloc calls. Pre-allocating an array of buckets, or using array-backed buckets, removes the hidden cost.

When to use

Numeric data with known bounded range. E.g., scores from 0 to 100, ages from 0 to 120.
Uniformly distributed inputs. Skewed inputs degrade performance.
You know the range up front. Otherwise you can’t choose buckets.

When the range isn’t known (or is huge), comparison sorts are usually better.

Comparison with radix sort

Both are distribution-based and avoid direct comparisons. The difference:

Bucket sort: distributes by value range. Each bucket sorts internally.
Radix sort: distributes by digit, processing one digit at a time. Buckets are 0–9 (or 0–9 plus a-f for hex, or whatever the radix). Multiple passes.

Bucket sort works on continuous-value data (floats); radix sort works on discrete digits.

Worked example

Sort arr = [29, 25, 3, 49, 9, 37, 21, 43]. Range is roughly 0–50; choose 5 buckets each spanning 10 values.

Distribute:

Bucket 0 (0-9): 3, 9
Bucket 1 (10-19): (none)
Bucket 2 (20-29): 29, 25, 21
Bucket 3 (30-39): 37
Bucket 4 (40-49): 49, 43

Sort each bucket (using insertion sort):

Bucket 0: [3, 9]
Bucket 1: []
Bucket 2: [21, 25, 29]
Bucket 3: [37]
Bucket 4: [43, 49]

Concatenate: [3, 9, 21, 25, 29, 37, 43, 49] — sorted.

Compared to insertion sort on the original array (which would be $O (n^{2}) = 64$ comparisons), bucket sort here uses 8 distributions + a few comparisons per bucket — roughly $O (n + k) = 13$ operations.

Choosing the bucket count

The right number of buckets is a trade-off:

Too few buckets: lots of elements per bucket, each bucket’s internal sort takes $O ((n / k)^{2})$ — degrades toward $O (n^{2})$ overall.
Too many buckets: most are empty, wasting memory.
Sweet spot: $k \approx n$ — each bucket has ~1 element on average, and the internal sort is trivial.

A common heuristic: $k = n$ (one bucket per expected element). For $n = 1000$ uniformly distributed values, use 1000 buckets.

Bucket sort for floating-point

Bucket sort shines for floating-point values uniformly distributed in some range. For floats in $[0, 1)$ :

int getBucketIndex(float value, int n) {
    return (int)(value * n);   // n buckets
}

Each bucket holds floats in a sub-range of width $1/ n$ . With $n$ buckets and $n$ uniformly-distributed values, expected bucket size is 1, and the sort is essentially $O (n)$ .

Used for sorting probabilities, normalized signal samples, color values, etc.

When the assumption fails

If values are non-uniformly distributed, bucket sort performance degrades:

Skewed distribution: most elements in one bucket → $O (n^{2})$ .
Heavy outliers: many empty buckets, wasted work.
Unknown range: have to scan to find min/max first ( $O (n)$ overhead), then sort ( $O (n)$ ). Overall still linear, but with worse constants.

Worst-case workloads need Quick sort or Merge sort.

Hybrid sorts

Real systems often use bucket-sort-style preprocessing followed by a comparison sort:

Distribute into buckets.
Sort each bucket with a fast comparison sort like Timsort or Quicksort.
Concatenate.

This combines bucket sort’s parallelism (each bucket can be sorted independently — easy to parallelize) with comparison sort’s worst-case guarantees. Used in some database engines and parallel sorting libraries.

For a related distribution sort that avoids the worst-case problem, see Radix sort and Counting sort.

Idriss Rami — Notes

Explorer