Quick sort randomization — expected O(n log n): Visual walkthrough

We only assume you know: quicksort picks a pivot, splits the array into "smaller than pivot" and "bigger than pivot", then repeats on each half. Everything else — every symbol, every fraction — we earn below.

Related vault ideas we lean on: Indicator Random Variables, Linearity of Expectation, Harmonic Number, and the un-randomized version Quicksort (deterministic).

Step 1 — Line up the numbers by their true sorted rank

WHAT we did: we gave every element a permanent label based on its position in sorted order.

WHY we did it: quicksort will shuffle the physical array around wildly, but the sorted ranks never change. If we count comparisons using these fixed labels, we can reason cleanly — "was $z_{3}$ ever compared to $z_{7}$ ?" is a question that survives all the chaos.

PICTURE: the top row is the messy input; the bottom row is the same values sorted, each wearing its $z$ -label.

Figure — Quick sort randomization — expected O(n log n)

Step 2 — Two elements are compared AT MOST once

Once an element has been the pivot, it is placed in its final spot and removed from all future recursion. So the pair ${z_{i}, z_{j}}$ can be compared zero or one times — never twice.

WHAT we did: we noticed each pair is compared at most once.

WHY it matters: "at most once" is exactly the condition that lets us use a 0/1 counter for each pair (Step 3). If pairs could be compared many times, a 0/1 flag would lose information.

PICTURE: three snapshots of the recursion. The pivot (yellow) touches everyone in its subarray; then it leaves the picture forever, and the two sides never talk to each other again.

Step 3 — Turn "were they compared?" into a number

This is an indicator random variable: a random quantity that is only ever $0$ or $1$ , acting as a yes/no answer wearing a number's clothes.

WHAT / WHY: we replaced the vague idea "number of comparisons" with an exact sum of yes/no switches. Counting-by-switches is the whole trick — it converts a messy process into arithmetic.

PICTURE: a grid of switches, one per pair $(i, j)$ ; lit switches are the comparisons that happened.

Step 4 — Expectation slides inside the sum (linearity)

Now, a switch that is $0$ or $1$ has a friendly average:

WHAT / WHY: the average of an indicator is simply the probability the event happens. So $E [X]$ has collapsed into a sum of probabilities — and probabilities are things we can compute.

$E [X] = i = 1 \sum n - 1 j = i + 1 \sum n Pr [z_{i} \leftrightarrow z_{j}]$

PICTURE: each grid cell now holds a number between 0 and 1 — its chance of lighting up — and $E [X]$ is the sum of all those numbers.

Step 5 — The crucial probability: who gets picked FIRST?

This is the heart of the derivation. We need $Pr [z_{i} \leftrightarrow z_{j}]$ .

Intuition WHY the first window-pivot is uniform among the

$j - i + 1$ elements This is the subtle step, so let's justify it carefully rather than assert it. Watch the recursion and pay attention only to which element gets picked as a pivot. Pivots outside the window $Z_{ij}$ do happen, but each such outside pivot is either bigger than all of $Z_{ij}$ or smaller than all of it (it can't be between two window elements, because the window is a contiguous block of ranks). So an outside pivot keeps the whole window together in one subarray — it never touches the internal order of who-among-the-window-goes-first. Therefore we may ignore (condition away) every outside pivot and ask only: given that a window element is finally chosen, which one is it? At that instant all $j - i + 1$ window elements are still sitting in the same subarray, and the algorithm picks the pivot uniformly at random from that subarray. By symmetry, each of the $j - i + 1$ window elements is equally likely to be that first-picked one — none is favoured over another. Exactly $2$ of those $j - i + 1$ equally-likely first-picks are "good" (the two endpoints $z_{i}, z_{j}$ ).

PICTURE: the window $Z_{ij}$ as a row of equally-tall bars (equal chance). The two endpoint bars are green (good: they get compared); every middle bar is red (bad: a middle pivot separates them).

Step 6 — Edge and degenerate cases (nothing left to chance)

PICTURE: the probability $\frac{2}{j - i + 1}$ plotted against window size $j - i + 1$ — starting at $1$ for adjacent pairs and decaying toward $0$ for distant pairs.

Step 7 — Add up all the probabilities

Plug the key probability into the boxed formula from Step 4:

$E [X] = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \frac{2}{j - i + 1}$

Now bound the inner sum by making it bigger and simpler (over-counting can only raise the total, which is fine for an upper bound). We enlarge the range from $k \leq n - i$ up to $k \leq n$ , and we replace each term $\frac{2}{k + 1}$ by the strictly larger $\frac{2}{k}$ :

$\sum_{k = 1}^{n - i} \frac{2}{k + 1} < \sum_{k = 1}^{n} \frac{2}{k} = 2 H_{n}$

Since the inner bound $2 H_{n}$ no longer depends on $i$ , the outer sum just repeats it $n - 1$ times:

$E [X] < 2 (n - 1) H_{n} = O (n lo g n)$

$2 (n - 1)$ — the $O (n)$ factor: one copy of $2 H_{n}$ per starting rank.
$H_{n} \approx ln n$ — the $O (lo g n)$ factor.
their product — the celebrated expected $O (n lo g n)$ , and it holds for every input, because nowhere did we assume anything about the input order — only about the coin flips.

PICTURE: the double sum drawn as stacked bars whose total area is squeezed under the curve $2 H_{n} \times (n - 1)$ .

Step 8 — Worked check: $n = 4$ by hand

The one-picture summary

The single figure below compresses all eight steps into one flow. Read it left to right; the caption under each box is the one-line "what happened here".

Walking the flow in prose: we start by naming elements by sorted rank so labels survive the shuffling; observe each pair is compared at most once, which licenses a 0/1 switch per pair; summing switches and averaging, linearity of expectation turns the average into a sum of probabilities; each probability is found by realising the first pivot inside the window decides everything, giving $Pr = \frac{2}{j - i + 1}$ ; summing that over all pairs and simplifying with the harmonic number yields $2 (n - 1) H_{n}$ , which is $O (n lo g n)$ . Eight boxes, one conclusion.

Recall Feynman retelling — explain the whole walkthrough to a friend

Line up all your numbers as if already sorted, and give each a name $z_{1}$ up to $z_{n}$ . Now ask, for any two of them: "will these two ever get directly compared?" Two numbers only ever get compared when one of them is the pivot, and a pivot only gets picked once and then leaves — so each pair meets at most once. That lets us flip a light switch $X_{ij}$ for each pair: on if they meet, off if not. The total number of comparisons is just the number of lit switches. The magic is linearity of expectation: the average number of lit switches is the sum of each switch's individual chance of being on. To find that chance, look at the block of numbers between the two, endpoints included. Whichever of those gets chosen as a pivot first decides everything: if it's one of the two ends, they get compared; if it's someone in the middle, that middle person stands between them and pushes them onto opposite sides forever. Since random pivots make each of those $j - i + 1$ numbers equally likely to be picked first (outside pivots keep the block together, so they don't tip the scales), and $2$ of them are the good ends, the chance is $\frac{2}{j - i + 1}$ . Add that up over all pairs, simplify with the harmonic number $H_{n} \approx ln n$ , and you land on $2 (n - 1) H_{n}$ , which is $O (n lo g n)$ — and crucially, we never once cared how the input was arranged, only about our own coin flips.

Recall Quick self-test

Neighbours in sorted order: chance compared? ::: $\frac{2}{2} = 1$ , always. Smallest vs largest of $n$ , i.e. $(z_{1}, z_{n})$ : chance compared? ::: $\frac{2}{n}$ . Why can we sum averages of dependent switches? ::: Linearity of expectation holds regardless of dependence. What decides if $z_{i}, z_{j}$ meet? ::: The first element of the window $Z_{ij}$ chosen as a pivot. Why is that first window-pivot uniform? ::: Outside pivots keep the window together; among the window elements the algorithm picks uniformly, so by symmetry each is equally likely to be first.

Compare with the guaranteed (non-expected) bounds of Merge Sort and the pivot-guarantee approach of Median of Medians; this whole analysis is a classic Las Vegas argument — always correct, running time random.