Bucket sort — uniform distributions: Visual walkthrough

We are going to answer one question: how much total work does sorting the buckets cost, on average? Every step below builds one piece of that answer.

Step 1 — What a bucket even is (the number line, chopped)

WHAT. Imagine every input value is a point sitting on a ruler that runs from $0$ up to (but not touching) $1$ . We write this range as $[0, 1)$ : the square bracket means " $0$ is included", the round bracket means " $1$ is not". We chop this ruler into $n$ equal-width pieces. Each piece is a bucket — a little box that will catch the points that land in its slice.

WHY. We chop into exactly $n$ pieces (where $n$ is how many numbers we have) because we are betting on one number per box. If that bet holds, sorting inside each box is trivial. Fewer boxes → crowded boxes → slow. Way more boxes → wasted empty boxes. So $n$ boxes is the balance point.

PICTURE. Look at figure s01. The ruler is split into $n$ equal slices. The width of each slice is $\frac{1}{n}$ — that is what "equal-width" means. A point $x$ sitting in the ruler falls into the slice numbered by how many full slices fit below it.

Figure — Bucket sort — uniform distributions

Step 2 — Scatter: the value is its own address

WHAT. Walk through the input once. For each value $x$ , compute $⌊ n \cdot x ⌋$ and drop $x$ into that box. No comparing $x$ against other values — we just read where it belongs.

WHY. This is the whole secret of bucket sort. A comparison sort is forced to ask "is $a < b$ ?" many times, and that questioning cannot beat $O (n lo g n)$ . Here we never ask that. We use the value itself as a postal address — the same trick Hashing uses. Because we skip comparisons at this stage, the $Ω (n lo g n)$ wall does not apply to us.

PICTURE. In figure s02, arrows fly from each input value straight down into its box. Notice how the ten arrows spread out — most boxes catch one, a couple catch two or three, some catch nothing. That unevenness is exactly what the rest of the proof must measure.

Step 3 — The one risky cost: sorting inside a box

WHAT. After scattering, each box holds a small pile. We sort each pile with Insertion sort. Let $n_{i}$ be the number of items in box $i$ . Sorting a pile of size $n_{i}$ with insertion sort costs, in the worst case, about $n_{i}^{2}$ steps.

WHY $n_{i}^{2}$ ? Insertion sort compares each new item against the ones already placed. In the worst case, item number 2 does 1 comparison, item 3 does 2, and so on — that adds up to $\frac{n _{i} ( n _{i} - 1 )}{2}$ , which grows like the square of the pile size. This squaring is the danger: if one box swallows everything, $n_{i} = n$ and we are back to $n^{2}$ — slow.

PICTURE. Figure s03 shows two boxes side by side: a lonely box with 1 item (cost $\approx 1$ ) versus a crowded box with 4 items (cost $\approx 16$ ). The crowded box costs far more than four lonely boxes — that is the penalty of clumping we must bound.

Everything now hinges on: how big is $\sum n_{i}^{2}$ on average?

Step 4 — Each item flips a coin: the Binomial appears

WHAT. Fix one box, say box $i$ . Each of the $n$ input values either lands in it or not. Because the input is drawn from a uniform distribution, every value is equally likely to hit any of the $n$ boxes. So the chance one value lands in box $i$ is $p = \frac{1}{n} .$

WHY this exact model? "Uniform" literally means no box is favoured. With $n$ equal-width slices covering the whole range, each slice grabs a $\frac{1}{n}$ share of the probability. And the values are drawn independently — one value's landing spot tells you nothing about the next. Independent coin flips, each with success chance $p$ , counted up, is precisely the Binomial distribution. So: $n_{i} \sim Binomial (n, \frac{1}{n}) .$

PICTURE. Figure s04 shows $n$ little coins, one per input value. Each coin lands "heads" (into box $i$ ) with probability $\frac{1}{n}$ . The number of heads is $n_{i}$ . The bar chart on the right is the shape of $Binomial (n, 1/ n)$ : a big spike at $0$ and $1$ , a small tail — most of the time you get $0$ or $1$ items, rarely more.

Step 5 — Mean and variance of one box's load

WHAT. Two facts about $n_{i} \sim Binomial (n, p)$ : $E [n_{i}] = n p, Var (n_{i}) = n p (1 - p) .$

$E [n_{i}]$ :: the average number of items in the box.
$Var (n_{i})$ :: the spread — how much the load wobbles around that average. Big variance = boxes are lumpy (some empty, some crowded).

WHY these formulas. Since $n_{i} = \sum_{j} I_{j}$ , its average is the sum of averages: $n \cdot p$ . For variance, because the switches are independent, variances add. One switch has variance $p (1 - p)$ (a quick fact about a single 0/1 coin), and there are $n$ of them, giving $n p (1 - p)$ .

PICTURE. Figure s05 plants the average $E [n_{i}]$ as a yellow line and draws the variance as the width of the spread around it. Watch the two arrows: as $n$ grows the average pins to $1$ , and the spread narrows toward $1$ too — the box load stays "about one, give or take one."

Now plug in our specific $p = \frac{1}{n}$ : $E [n_{i}] = n \cdot \frac{1}{n} = 1, Var (n_{i}) = n \cdot \frac{1}{n} (1 - \frac{1}{n}) = 1 - \frac{1}{n} .$

Read that in plain words: on average exactly one item per box, wobbling by just under one. Exactly the picture we bet on in Step 1.

Step 6 — Turning mean+variance into $E [n_{i}^{2}]$

WHAT. The sort cost was $n_{i}^{2}$ , so we need the average of the square, $E [n_{i}^{2}]$ — not the square of the average. These differ, and the gap between them is exactly the variance. For any random quantity — call the generic placeholder $X$ , and in a moment we set $X = n_{i}$ — the definition of variance rearranges to: $E [X^{2}] = Var (X) + (E [X])^{2} .$ Applying it with $X = n_{i}$ (our box load) gives exactly what we need: $E [n_{i}^{2}] = Var (n_{i}) + (E [n_{i}])^{2} .$

WHY this identity. Variance is defined as "the average squared distance from the mean," $Var (X) = E [X^{2}] - (E [X])^{2}$ . Rearranging gives the line above. We need it because clumping (variance) is precisely the extra cost that squaring exposes — the identity lets us pay for it explicitly.

PICTURE. Figure s06 stacks two blocks: a green block of height $(E [n_{i}])^{2} = 1$ (the cost if boxes were perfectly even) and a red block of height $Var (n_{i}) = 1 - \frac{1}{n}$ (the extra cost that randomness/clumping adds). Their sum is the true expected square work.

$E [n_{i}^{2}] = clumping penalty (1 - \frac{1}{n}) + ideal even case 1^{2} = 2 - \frac{1}{n} .$

The headline: $E [n_{i}^{2}] < 2$ , a constant. It does not grow with $n$ .

Step 7 — Summing over all boxes: the linear finish

WHAT. Take the honest cost from Step 3, $T = c n + \sum_{i = 0}^{n - 1} c^{'} n_{i}^{2}$ , and average it. Two rules of expectation do all the work:

$E [T] = E [c n + \sum_{i = 0}^{n - 1} c^{'} n_{i}^{2}] = c n + c^{'} \sum_{i = 0}^{n - 1} E [n_{i}^{2}] .$

Linearity of expectation :: the average of a sum is the sum of the averages, even when the $n_{i}$ are not independent of each other. This is the rule that lets us slide the $E [\cdot]$ inside the $\sum$ , turning $E [\sum n_{i}^{2}]$ into $\sum E [n_{i}^{2}]$ . (We do not need independence between boxes — linearity holds regardless.)
The constant $c n$ has no randomness, so its average is itself.

WHY it collapses. From Step 6, every $E [n_{i}^{2}] = 2 - \frac{1}{n}$ , a fixed number. Substitute it: $E [T] = c n + c^{'} \sum_{i = 0}^{n - 1} (2 - \frac{1}{n}) = c n + c^{'} n (2 - \frac{1}{n}) = c n + c^{'} (2 n - 1) .$ Both pieces are of the form "constant times $n$ " (plus a lower-order $- c^{'}$ ), so $E [T] = O (n) .$ Notice we only invoked big- $O$ at the very end, on an ordinary number — never inside an expectation.

PICTURE. Figure s07 lines up all $n$ boxes, each carrying its little constant cost bar (height $\approx 2$ ). The total is just $n$ short bars stacked — a straight line growing with $n$ , never bending upward. That straight line is linear time.

Step 8 — The degenerate case: what if the input is NOT uniform?

WHAT. Everything above rested on $p = \frac{1}{n}$ for every box. If the input is skewed or adversarial, that assumption dies. In the extreme, all $n$ values crash into one box: that box has $n_{i} = n$ , and insertion sort on it costs $n^{2}$ .

WHY it matters. The $O (n)$ result is an average over uniform inputs, not a promise for every input. The proof's engine — "each box gets $\frac{1}{n}$ of the mass" — simply isn't true when data clumps. This is the same warning the parent note gives: spread evenly = speedy; clumped = crawls.

PICTURE. Figure s08 contrasts the two worlds: on the left, ten arrows fan out evenly (the $O (n)$ dream); on the right, all ten arrows dive into a single box (the $O (n^{2})$ nightmare). Same algorithm, wildly different cost — decided entirely by the input's shape.

The one-picture summary

Figure s09 overlays the two forces that fight inside $\sum n_{i}^{2}$ : the ideal even cost (a flat green baseline at $n$ , one unit per box) and the actual expected cost including clumping (a red curve landing at $2 n - 1$ ). The gap between them — the variance term — never widens into a new power of $n$ ; it stays a constant multiple. That single picture is why the average total work is $\approx 2 n$ and not $n^{2}$ : clumping only ever doubles the baseline, it never squares it.

Recall Feynman retelling — the walkthrough in plain words

We laid a ruler from 0 to 1 and chopped it into $n$ equal boxes. Every number, instead of being compared, just walked to the box matching its own value — the value is its own address, so we dodged the comparison speed limit. Because the numbers were spread evenly, each box expected about one number. But randomness makes boxes lumpy — some get two, some get none. Sorting inside a box costs the square of its load, so lumpiness is what we feared. We modelled each box's load as counting heads in $n$ coin flips (a Binomial), found its average is $1$ and its wobble is just under $1$ , and combined them via $E [X^{2}] = Var (X) + (E [X])^{2}$ : the average squared load is $2 - \frac{1}{n}$ — a tiny constant. Then linearity of expectation let us add that constant across all $n$ boxes to get $\approx 2 n$ — a straight line, linear time. The one catch: if the numbers clump into a single box, the whole story collapses to $n^{2}$ . Even spread = fast; clumped = slow.

Recall checkpoint

Recall Quick self-test

Which distribution models one box's load, and with what parameters? ::: $Binomial (n, 1/ n)$ — $n$ independent items each landing with probability $1/ n$ . Why do we need $E [n_{i}^{2}]$ and not $(E [n_{i}])^{2}$ ? ::: Insertion sort cost is $n_{i}^{2}$ , so we need the average of the square; the two differ by exactly the variance. What does the identity $E [X^{2}] = Var (X) + (E [X])^{2}$ contribute? ::: It splits the squared cost into the ideal even-load part $(1)$ plus the clumping penalty (the variance). Which rule lets us turn $E [\sum n_{i}^{2}]$ into $\sum E [n_{i}^{2}]$ ? ::: Linearity of expectation — it holds even without independence between boxes. Numerically, what is $E [n_{i}^{2}]$ and why is that the punchline? ::: $2 - 1/ n$ , a constant below $2$ — so summing over $n$ boxes gives $O (n)$ . Where in the derivation does uniformity get used? ::: In setting $p = 1/ n$ equally for every box (Step 4); skewed input breaks this and gives $O (n^{2})$ .

Connections

Bucket sort — uniform distributions — the parent note whose $O (n)$ result this page derives visually.
Binomial distribution — supplies the box-load model and its mean/variance in Steps 4–5.
Insertion sort — the per-box sort whose $n_{i}^{2}$ cost drives the whole analysis.
Comparison sort lower bound — the $Ω (n lo g n)$ wall we sidestep by using value-as-address.
Hashing — same "value is its own address" idea, different goal.
Counting sort — the extreme case of one item per bucket over integers.
Radix sort — repeated bucketing, digit by digit.