Lesson 20 · Core algorithms

Bucket Sort: Distribution and Spread

Scatter values into ranges, sort each small bucket, then read the buckets back in order.

How Bucket Sort Works

Bucket sort takes the opposite approach to every comparison sort: instead of ordering the whole array at once, it first breaks the input into ranges cheaply, then sorts each small range on its own. Because a value's bucket is computed by arithmetic rather than by comparison, the scattering phase is a single linear pass.

Choose the bucket count usually n buckets for n values, so each is expected to hold roughly one item.
Map each value to a bucket an index computed from the value's position in the range, so no comparison is needed to place it.
Scatter every value one pass over the input drops each item into its bucket, which is O(n).
Sort each bucket insertion sort is the usual choice, because a bucket that holds two or three items sorts almost instantly.
Concatenate in bucket order reading bucket 0, then 1, and so on yields the fully sorted array.

Scattering is arithmetic, not comparison, so it is one linear pass
Each bucket is sorted independently, usually by insertion sort
Buckets are read back in index order, so no merge step is needed
Works on floats, which counting sort cannot handle

Why Spread Decides Everything

The average case is O(n + n²/k + k), which becomes O(n) when the bucket count k is chosen as n and the values are spread uniformly. That is the headline result, and it rests entirely on an assumption about the input, not about the algorithm — a rare and important distinction.

If the data is skewed, the assumption collapses. Put every value into a single bucket and the algorithm degenerates into whatever sort was chosen for that bucket, applied to the whole array: O(n²) with insertion sort. Nothing about bucket sort protects against this, because the bucket index is computed from the value's position in the range, and a range dominated by outliers spreads nothing.

This makes bucket sort unusual among the sorts on this course. Quicksort's worst case can be mitigated by pivot choice; merge sort has no bad input at all. Bucket sort's performance is a property of the data you happen to receive, which is why it is used where the distribution is known in advance — sensor readings in a fixed range, normalised scores, random floats in [0, 1) — and avoided where it is not.

Bucket sort's cost is a property of the input, not of the algorithm
Distribution	Buckets used	Cost	Why
Uniform over the range	all k	O(n)	About one value per bucket
Mildly clustered	most	O(n) to O(n log n)	A few buckets hold several items
All values close together	1	O(n squared)	One bucket holds everything
One extreme outlier	2	O(n squared)	The range stretches, everything else collapses into one bucket

O(n) average assumes uniform spread — an assumption about the data
O(n squared) worst case when one bucket takes everything
A single outlier can stretch the range and ruin the spread
Use it when the distribution is known, not on arbitrary input

Implementation

Sort with bucket sort

def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1
        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1
        values[j + 1] = current
    return values


def bucket_sort(values):
    if not values:
        return values
    count = len(values)
    buckets = [[] for _ in range(count)]
    # The bucket index is arithmetic, so scattering is one linear pass.
    for value in values:
        index = min(int(value * count), count - 1)
        buckets[index].append(value)
    output = []
    for bucket in buckets:
        output.extend(insertion_sort(bucket))
    return output


print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94]))

#include <iostream>
#include <vector>
using namespace std;
// Insertion sort is the conventional per-bucket choice: stable, and fast on
// the two or three items a bucket usually holds.
void insertionSort(vector<double>& values) {
    for (size_t i = 1; i < values.size(); i++) {
        double current = values[i];
        int j = (int)i - 1;
        while (j >= 0 && values[j] > current) {
            values[j + 1] = values[j];
            j--;
        }
        values[j + 1] = current;
    }
}
vector<double> bucketSort(const vector<double>& values) {
    if (values.empty()) return values;
    int count = (int)values.size();
    vector<vector<double>> buckets(count);
    // The bucket index is arithmetic, so scattering is one linear pass.
    for (double value : values) {
        int index = min((int)(value * count), count - 1);
        buckets[index].push_back(value);
    }
    vector<double> output;
    for (auto& bucket : buckets) {
        insertionSort(bucket);
        for (double v : bucket) output.push_back(v);
    }
    return output;
}
int main() {
    for (double v : bucketSort({0.78, 0.17, 0.39, 0.26, 0.72, 0.94})) cout << v << " ";
    cout << endl;
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BucketSort {
    // Insertion sort is the conventional per-bucket choice: stable, and fast
    // on the two or three items a bucket usually holds.
    static void insertionSort(List<Double> values) {
        for (int i = 1; i < values.size(); i++) {
            double current = values.get(i);
            int j = i - 1;
            while (j >= 0 && values.get(j) > current) {
                values.set(j + 1, values.get(j));
                j--;
            }
            values.set(j + 1, current);
        }
    }
    static double[] bucketSort(double[] values) {
        if (values.length == 0) return values;
        int count = values.length;
        List<List<Double>> buckets = new ArrayList<>();
        for (int i = 0; i < count; i++) buckets.add(new ArrayList<>());
        // The bucket index is arithmetic, so scattering is one linear pass.
        for (double value : values) {
            int index = Math.min((int) (value * count), count - 1);
            buckets.get(index).add(value);
        }
        double[] output = new double[count];
        int at = 0;
        for (List<Double> bucket : buckets) {
            insertionSort(bucket);
            for (double v : bucket) output[at++] = v;
        }
        return output;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(
        bucketSort(new double[]{0.78, 0.17, 0.39, 0.26, 0.72, 0.94})));
    }
}

Watch it run

Step through it

Running on [0.78, 0.17, 0.39, 0.26, 0.72, 0.94]

Output

Against Counting and Radix Sort

All three of these avoid comparisons, and they are easy to confuse. Counting sort needs exact integer keys and a small range, because it allocates one counter per possible value. Radix sort removes the range limit by processing one digit at a time, but still needs keys decomposable into digits. Bucket sort needs neither: it only needs to compute which range a value falls into, so it handles floating-point values and any orderable key.

The trade is that bucket sort gives up the guarantee. Counting and radix sort are linear on any input meeting their key requirements; bucket sort is linear only when the input cooperates. In exchange it is the only one of the three that copes with continuous values.

A practical note worth carrying: the sort used inside each bucket must be stable if the overall sort needs to be stable, and insertion sort is stable, which is one more reason it is the conventional choice.

Counting sort: exact integer keys, small range, linear guaranteed
Radix sort: digit-decomposable keys, linear guaranteed
Bucket sort: any orderable key including floats, linear only if spread
Stability comes from the per-bucket sort, so use a stable one

On Paper: Sorting [0.78, 0.17, 0.39, 0.26, 0.72, 0.94]

Sort six values in [0, 1) with six buckets, so bucket index is floor(value × 6). This is the textbook setup, and the arithmetic is worth doing once by hand.

Input: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94]
Six buckets, index = floor(value × 6)
Each bucket sorted with insertion sort

0.78 × 6 = 4.68, so it goes to bucket 4. 0.17 × 6 = 1.02 → bucket 1. 0.39 → bucket 2, 0.26 → bucket 1, 0.72 → bucket 4, 0.94 → bucket 5. Buckets 0 and 3 stay empty, buckets 1 and 4 each hold two values, and the rest hold one.

Bucket 1 holds [0.17, 0.26] — already in order, so insertion sort does one comparison and no shifts. Bucket 4 holds [0.78, 0.72], which needs one swap. Reading buckets 0 through 5 in order and skipping the empty ones gives [0.17, 0.26, 0.39, 0.72, 0.78, 0.94], with six scatter operations and two tiny sorts.

Buckets 1 and 4 hold two values; buckets 0 and 3 stay empty
Only bucket 4 needs an actual swap
Concatenating in bucket order needs no merge
Empty buckets cost nothing to skip

How Bucket Sort Works

Why Spread Decides Everything

Sort with bucket sort

Step through it

Against Counting and Radix Sort

On Paper: Sorting [0.78, 0.17, 0.39, 0.26, 0.72, 0.94]

Continue this course

Sorting Algorithms: Methods and Performance

Bubble Sort: Passes, Swaps and Complexity

Selection Sort: Scan, Swap and Cost