Bucket sort — uniform distributions

WHAT it is

The assumption that makes it fast: inputs are drawn from a uniform distribution over a known interval, so buckets fill evenly.

WHY it works — derive the expected time from scratch

We want the expected total cost. The scatter, concatenation, and bucket creation are each $O(n)$. The only risky part is sorting the buckets, since insertion sort on a bucket of size $m$ costs $O(m^2)$.

Let $n_i$ = number of elements landing in bucket $i$. Total sort cost: $T = O(n) + \sum_{i=0}^{n-1} O(n_i^2)$

Take expectation: $E[T] = O(n) + \sum_{i=0}^{n-1} O\big(E[n_i^2]\big)$

Now we need $E[n_i^2]$. Each of the $n$ elements lands in bucket $i$ independently with probability $p = 1/n$ (uniform input → equal chance per bucket). So $n_i \sim \text{Binomial}(n, 1/n)$.

Using the identity $E[X^2]=\operatorname{Var}(X)+\big(E[X]\big)^2$: $E[n_i^2] = np(1-p) + (np)^2$

Plug $p = 1/n$: $E[n_i^2] = n\cdot\frac{1}{n}\left(1-\frac{1}{n}\right) + \left(n\cdot\frac1n\right)^2 = \left(1-\frac1n\right) + 1 = 2 - \frac1n$

Why this is the punchline: $E[n_i^2]$ is a constant ($<2$), not growing with $n$. So: $E[T] = O(n) + \sum_{i=0}^{n-1} O\!\left(2-\frac1n\right) = O(n) + O(n) = \boxed{O(n)}$

HOW to implement it

def bucket_sort(a):           # a: list of floats in [0, 1)
    n = len(a)
    buckets = [[] for _ in range(n)]      # n empty buckets
    for x in a:
        buckets[int(n * x)].append(x)     # scatter: index = floor(n*x)
    out = []
    for b in buckets:
        b.sort()                          # insertion sort in practice
        out.extend(b)                     # concatenate in order
    return out

Why int(n*x)? Stretching $[0,1)$ by $n$ maps the value directly to a bucket address, so equal-width slots correspond to equal value-ranges.

When it FAILS (the steel-man)

Recall checkpoint

Connections

• Counting sort — bucket sort with bucket size 1 over integers.
• Radix sort — repeated bucketing digit by digit.
• Insertion sort — the per-bucket sort, fast on tiny/near-sorted lists.
• Comparison sort lower bound — why non-comparison sorts can beat $n\log n$.
• Binomial distribution — supplies $E[n_i^2]$ in the analysis.
• Hashing — same "value-as-address" idea, different goal.

Concept Map

Hinglish (regional understanding)