Exercises — Bucket sort — uniform distributions

WHAT: apply the index formula $\lfloor n\cdot x\rfloor$. WHY: stretching $[0,1)$ by $n=5$ turns the value into an address; the floor picks the slot. $\lfloor 5\cdot 0.53\rfloor =\lfloor 2.65\rfloor =2$ Answer: bucket 2. (Values in $[0.4,0.6)$ all map here — check: $0.4\cdot 5=2$, $0.6\cdot 5=3$.)

A uniform distribution over a known range. It guarantees each element is equally likely to land in any bucket, so buckets fill evenly — about one item each. See Binomial distribution for why "equally likely per bucket" gives $n_i\sim \text{Binomial}(n,1/n)$.

False — it does not violate it; the bound simply does not apply. The Comparison sort lower bound only constrains algorithms that decide order by comparing pairs. Bucket sort's scatter step uses the value as an address (like Hashing), not a comparison, so it is outside the theorem's scope.

Step — scatter with index $=\lfloor 4x\rfloor$:

• $0.10\to \lfloor 0.4\rfloor =0$
• $0.60\to \lfloor 2.4\rfloor =2$
• $0.30\to \lfloor 1.2\rfloor =1$
• $0.90\to \lfloor 3.6\rfloor =3$

Buckets: [0]=[0.10], [1]=[0.30], [2]=[0.60], [3]=[0.90]. Step — sort each: each has one element → nothing to do. Step — concatenate in order: [0.10, 0.30, 0.60, 0.90] ✅. A textbook "one item per bucket" case — see the histogram in the figure below.

WHY normalize first: the index formula assumes $[0,1)$. We rescale the value into $[0,1)$ using $\frac{x-lo}{hi-lo}$, then bucket. $\text{index}=\lfloor 5\cdot \frac{17-10}{20-10}\rfloor =\lfloor 5\cdot 0.7\rfloor =\lfloor 3.5\rfloor =3$ Answer: bucket 3.

Index $=\lfloor 10x\rfloor$:

• $0.12,0.17\to 1$
• $0.21,0.23,0.26\to 2$

Bucket 1 holds 2 items; bucket 2 holds 3 items; all others empty. Largest load $n_i=3$, so the costliest per-bucket Insertion sort handles only 3 elements — cheap.

WHAT tool: the identity $E[X^2]=\mathrm{Var}(X)+(E[X]{)}^2$, because we know mean and variance of a Binomial but not $E[X^2]$ directly. With $p=1/n=1/8$: $E[n_i]=np=1,\mathrm{Var}(n_i)=np(1-p)=1\cdot \frac{7}{8}=\frac{7}{8}$ $E[n_i^2]=\frac{7}{8}+1^2=\frac{15}{8}=1.875$ This matches the general formula $2-\frac{1}{n}=2-\frac{1}{8}=1.875$. Constant, below 2 — the reason total work stays linear.

Linearity of expectation: $E\left[{\sum }_i{n}_i^2\right]={\sum }_{i}E[n_i^2]=8\cdot 1.875=15$. Compare to the "perfect" one-per-bucket world where $\sum n_i^2=n=8$. The extra $7$ is the clumping penalty from variance — still $O(n)$, not $O(n^2)$.

Put every value inside a single slot's range. Bucket $0$ owns $[0,0.25)$. Choose [0.01, 0.05, 0.10, 0.20]: $\lfloor 4\cdot 0.01\rfloor =\lfloor 4\cdot 0.05\rfloor =\lfloor 4\cdot 0.10\rfloor =\lfloor 4\cdot 0.20\rfloor =0$ All 4 land in bucket 0. That bucket's Insertion sort costs $O(n^2)$. Worst case $O(n^2)$ — the histogram (right panel below) shows the single tall spike vs. the flat uniform case.

With $b$ buckets, creation + concatenation cost $O(b)$; scatter costs $O(n)$; each $n_i\sim \text{Binomial}(n,1/b)$ so expected sort work is ${\sum }_{i}E[n_i^2]$. $E[n_i^2]=\underset{\text{Var}}{\underbrace{\frac{n}{b}\left(1-\frac{1}{b}\right)}}+\underset{{\text{mean}}^2}{\underbrace{{\left(\frac{n}{b}\right)}^2}},{\sum }_{i=0}^{b-1}E[n_i^2]=n\left(1-\frac{1}{b}\right)+\frac{n^2}{b}$ Total: $E[T]=O(b)+O(n)+O(n+\frac{n^2}{b})$.

• $b=10^6$: the $O(b)=O(10^6)$ term dominates $n=10^3$ → wasted work on empty buckets.
• $b=n=1000$: $\frac{n^2}{b}=n$, everything is $O(n)$. ✅

Sweet spot $b\approx n$ — one bucket per expected element.

Two requirements:

1. Scatter in original order and append — so within a bucket, earlier elements sit earlier. (Insertion sort preserves this if it's a stable sort.)
2. Per-bucket sort must be stable. Insertion sort is stable, so use it (not an unstable quicksort).

Because concatenation reads buckets left-to-right and each bucket kept insertion order among equal keys, the whole output is stable. This is exactly why Counting sort (bucket sort with size-1 integer buckets) is famously stable.

Bucketing on the leading digit is MSD (most-significant-digit) radix sort's first pass: it groups by high-order digit. Within a bucket, elements are not yet fully ordered — only their leading digit agrees. What breaks after one pass: two values 0.412 and 0.418 share bucket 4 but stay unsorted relative to each other. Radix sort fixes this by recursively bucketing each bucket on the next digit (or LSD radix does it back-to-front with a stable pass). Bucket sort's own fix is simpler: sort each bucket directly with insertion sort.

WHAT tool: the balls-into-bins result, driven by the Binomial distribution tail. Each $n_i\sim \text{Binomial}(n,1/n)\approx \text{Poisson}(1)$ for large $n$. Estimate: $\underset{i}{\max }{n}_i=\Theta \left(\frac{\log n}{\log \log n}\right)$ with high probability. Intuition: with $n$ nearly-independent Poisson(1) buckets, the tail probability $P(n_i\ge k)\approx \frac{1}{k!}$; the largest of $n$ such draws is around the $k$ where $n/k!\approx 1$, i.e. $k!\approx n$, giving $k\approx \frac{\log n}{\log \log n}$. Why it matters: even the worst bucket is only poly-logarithmic, so no single insertion sort blows up the linear expectation — the average $O(n)$ is robust, not luck.

Idea: make buckets equal-probability, not equal-width. Use the cumulative distribution $F(x)={\int }_0^{x}f(t)dt$, which maps $x$ to "fraction of mass below $x$", so $F(x)$ is uniform on $[0,1)$ by construction. Rule: bucket index $=\lfloor n\cdot F(x)\rfloor$. Why it works: because $F(X)$ is uniform for any continuous $X$ (the "probability integral transform"), each bucket now receives probability $1/n$ → $n_i\sim \text{Binomial}(n,1/n)$ again → the same $E[n_i^2]=2-\frac{1}{n}$ → expected $O(n)$ even on skewed data. Cost of the fix: you must know (or estimate) $F$. If you don't, skewed data reverts to the $O(n^2)$ worst case.

Index $=\lfloor 6x\rfloor$:

• $0.99\to \lfloor 5.94\rfloor =5$
• $0.02\to \lfloor 0.12\rfloor =0$
• $0.51\to \lfloor 3.06\rfloor =3$
• $0.50\to \lfloor 3.00\rfloor =3$
• $0.98\to \lfloor 5.88\rfloor =5$
• $0.03\to \lfloor 0.18\rfloor =0$

Buckets (append order preserved):

• [0] = [0.02, 0.03]
• [3] = [0.51, 0.50]
• [5] = [0.99, 0.98]

Sort each: [0]=[0.02,0.03], [3]=[0.50,0.51], [5]=[0.98,0.99]. Concatenate: [0.02, 0.03, 0.50, 0.51, 0.98, 0.99] ✅ fully sorted. Stability check: no duplicate keys here, but note $0.51$ and $0.50$ shared bucket 3 and were reordered by value (correct) — stability only concerns equal keys, which are untouched.