Quick sort — Lomuto - Hoare partition, pivot strategies, expected O(n log n), worst case: Visual walkthrough

Step 1 — What "one partition" actually costs

WHAT. Take an array segment. Pick one element — the pivot, the value we compare everything against. Partitioning means: walk across the whole segment once, comparing each element to the pivot and pushing smaller ones left, larger ones right.

WHY. Before we can count the total work, we must know the cost of the smallest unit of work — a single partition. Everything else is just many partitions stacked in a tree.

PICTURE. Below, the segment has $m = 8$ boxes. The scan pointer (orange) visits every box exactly once. That is $m$ comparisons — one arrow per box. So:

$cost of partitioning C (m) = tiny fixed cost per comparison c \cdot number of boxes we walk past m$

The symbol $c$ is just "the time for one compare-and-maybe-swap"; $m$ is the segment length. Read it as: partition cost grows in a straight line with segment size.

Step 2 — Stacking partitions into a tree

WHAT. After one partition the pivot is fixed, and we are left with two smaller segments — the "less" side and the "greater" side. Each becomes a new partition problem. Draw a node for every partition; connect a parent to its two children.

WHY. The total cost of quicksort is the sum of all partition costs across all nodes. If we can add up the costs level-by-level, we can find the total. So we need the shape of this tree.

PICTURE. The root handles all $n$ boxes. Its two children together also cover (almost) all $n$ boxes — the pivot dropped out, but everything else is redistributed. So each full level of the tree costs about $c n$ : the same $n$ elements, just chopped into more pieces.

$cost of one level \approx per box c \cdot every element appears once per level n$

The total is therefore:

$T (n) \approx cost per level c n \times tree height (number of levels)$

Everything now hinges on one question: how tall is the tree? That is the whole game.

Step 3 — The dream split: exactly in half

WHAT. Suppose every pivot lands dead centre, so each segment of size $m$ becomes two of size $m /2$ .

WHY. This is the best possible shape. If we understand it, we have a floor to compare everything else against.

PICTURE. Sizes go $n \to n /2 \to n /4 \to \dots \to 1$ . How many halvings until we reach a single box? That is exactly the question == $lo g_{2}$ == answers: "how many times do I halve $n$ to reach $1$ ?"

$height = lo g_{2} n ⟺ n \cdot l o g_{2} n times \frac{1}{2} \cdot \frac{1}{2} \dots \frac{1}{2} = 1$

Why $lo g$ and not, say, subtraction? Because at each step we divide the size, we don't subtract a fixed chunk. Repeated division is what a logarithm counts. Plugging the height into Step 2:

$T (n) \approx c n \cdot lo g_{2} n = Θ (n lo g n)$

Term by term: $c n$ is the cost of one level (Step 2); $lo g_{2} n$ is the number of levels (this step). Multiply → the famous $n lo g n$ .

Step 4 — You don't need exact halves

WHAT. Real pivots are rarely perfect. Suppose every split is a lopsided $\frac{1}{10}$ vs $\frac{9}{10}$ instead of $\frac{1}{2}$ vs $\frac{1}{2}$ .

WHY. If quicksort only worked on perfect halves it would be useless — random pivots never split perfectly. We must show that any constant fraction is good enough.

PICTURE. Follow the longest branch (always the $9/10$ side). Sizes go $n \to \frac{9}{10} n \to (\frac{9}{10})^{2} n \to \dots$ . The chain ends when $(\frac{9}{10})^{h} n = 1$ , giving:

$h = lo g_{10/9} n = Θ (lo g n)$

The base of the log changed from $2$ to $10/9$ — but a change of log base is only a constant multiplier, so the height is still $Θ (lo g n)$ . The picture shows the two branch lengths: the short $1/10$ branch dies fast; even the long $9/10$ branch reaches bottom in logarithmically many steps.

Key visual takeaway: as long as the split ratio doesn't drift toward "0 vs everything," the tree stays short. This is the buffer that makes random pivots safe.

Step 5 — Averaging over random pivots: the "gap" trick

WHAT. Instead of guessing a split ratio, average over all pivot choices. Line the elements up in sorted order and name them $z_{1} < z_{2} < \dots < z_{n}$ (just labels for "the smallest," "the 2nd smallest," …). Ask: do $z_{i}$ and $z_{j}$ ever get compared?

WHY. Total comparisons = total work. Counting comparisons directly is a nightmare of nested recursion. But if we ask the yes/no question "are these two ever compared?" for every pair, we can add up tiny probabilities instead. This is the indicator variable trick.

PICTURE. Consider the gap ${z_{i}, z_{i + 1}, \dots, z_{j}}$ — all sorted values between the two, inclusive. Whichever of these is chosen as a pivot first decides their fate:

If the first pivot from the gap is $z_{i}$ or $z_{j}$ → they are compared (pivot vs the other, directly).
If it is anyone strictly between → that pivot splits them into different subarrays, and they never meet again.

So the pair is compared only when the winner of the gap is one of the two endpoints: $2$ good choices out of $(j - i + 1)$ equally likely first-picks.

$Pr [z_{i} and z_{j} compared] = 2 endpoints out of gap size \frac{2}{j - i + 1}$

$2$ = the two endpoints; $j - i + 1$ = how many elements sit in the gap (each equally likely to be picked first, since the pivot is random).

Step 6 — Summing the tiny probabilities into $2 n ln n$

WHAT. Add the per-pair probabilities over every pair to get the expected total comparisons.

WHY. Expectation of a sum = sum of expectations (this holds even when events overlap — the magic of linearity). So the messy dependent recursion becomes a plain double sum.

PICTURE. Group pairs by their gap width $k = j - i + 1$ . For a fixed left endpoint $z_{i}$ , the gap widths run $k = 2, 3, \dots$ , and each contributes $2/ k$ . The picture stacks these shrinking $2/ k$ bars — they are exactly a harmonic series.

$E [comparisons] = \sum_{i < j} \frac{2}{j - i + 1} \leq 2 \sum_{i = 1}^{n} = H_{n} k = 1 \sum n \frac{1}{k} = 2 n H_{n}$

$i < j \sum$ = over all pairs of elements.
$\frac{2}{j - i + 1}$ = each pair's compare-probability from Step 5.
$H_{n} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ = the $n$ -th harmonic number, the total height of all those shrinking bars.

The bars of $1/ k$ hug the curve $1/ x$ , and the area under $1/ x$ from $1$ to $n$ is $ln n$ . That is why $H_{n} \approx ln n$ :

$E [comparisons] \approx 2 n ln n \approx 1.39 n lo g_{2} n = Θ (n lo g n)$

The constant $1.39$ comes from converting natural log to base-2 log ( $1/ ln 2 \approx 1.44$ , times the $2$ ... shown exactly in the verify block).

Step 7 — The degenerate case: worst-possible pivots

WHAT. Now break it on purpose. Suppose every pivot is the smallest remaining element (this happens with last-element pivot on an already-sorted array).

WHY. Contract rule: cover the limiting case. The reader must see why the same algorithm collapses to $n^{2}$ .

PICTURE. A perfect pivot removes the middle and splits in half. The worst pivot removes only itself — one endpoint — leaving a segment of size $m - 1$ . The tree is no longer bushy; it's a single dangling chain of height $n$ . The level costs shrink only by $1$ each time:

$T (n) = T (n - 1) + c n = c n + c (n - 1) + \dots + c \cdot 1 = c \cdot \frac{n ( n + 1 )}{2} = Θ (n^{2})$

$T (n - 1)$ = the lone child, only one element smaller.
$+ c n$ = we still scanned all $n$ boxes to peel off one.
The sum $n + (n - 1) + \dots + 1$ is the classic triangle $\frac{n ( n + 1 )}{2}$ — quadratic.

Compare the two trees side by side: the balanced tree is short and wide ( $lo g n$ tall); the degenerate tree is tall and thin ( $n$ tall). Same per-level idea, disastrously different height. This is exactly the case Introsort escapes by bailing out to Heap Sort once the recursion gets too deep, and random pivots make astronomically unlikely.

The one-picture summary

Everything on one canvas: partition cost is a straight line ( $c n$ per level, Step 1–2); the height is decided by the pivot. Good/lucky pivots → short $lo g n$ tree → $n lo g n$ (Steps 3–6). Adversarial pivots → tall $n$ chain → $n^{2}$ (Step 7). The "gap" probability $\frac{2}{j - i + 1}$ is the bridge that turns "average over random pivots" into the clean harmonic sum $2 n H_{n}$ .

Recall Feynman retelling — say it out loud in plain words

Picture sorting as chopping a line of numbers. You point at one number — the pivot — and shove everything smaller to its left, bigger to its right. That one sweep costs one look per number, so it's a straight-line cost, call it $c n$ .

Now you've got two smaller lines. Do the same to each. Draw this as a family tree of chops. Every full row of the tree touches all $n$ numbers once, so every row costs about $c n$ . The only thing left to figure out is: how many rows tall is the tree?

If your pivot always lands near the middle, each line halves, and halving $n$ down to $1$ takes only $lo g_{2} n$ steps — a short, fat tree — so you pay $c n \times lo g n = n lo g n$ . Even a sloppy 10-90 split just changes the log's base, which is a harmless constant, so you're still fine.

To handle random pivots without guessing a ratio, use the gap trick: sort the values in your head as $z_{1}, z_{2}, \dots$ . Two of them, $z_{i}$ and $z_{j}$ , only ever get compared if the first pivot picked from the block between them happens to be one of those two endpoints — that's $2$ winners out of $(j - i + 1)$ candidates. Add that little $\frac{2}{j - i + 1}$ over every pair and you get $2 n H_{n}$ , and $H_{n}$ is just $1 + \frac{1}{2} + \frac{1}{3} + \dots$ , which piles up to about $ln n$ . So the average is $2 n ln n \approx 1.39 n lo g_{2} n$ .

The disaster case: if the pivot is always the tiniest element, each chop peels off just one number, so the tree is a long skinny chain $n$ rows deep, and $c n$ per row gives $n + (n - 1) + \dots = n^{2}$ . Fix it by picking pivots at random or bailing to heapsort when the tree gets too deep.

Recall Quick self-check

Why does each level of the recursion tree cost about $c n$ ? ::: Because the elements are just redistributed among that level's segments — every element (bar the pivots) appears exactly once per level, and partitioning scans each once. Why is even a 1:9 split still $O (n lo g n)$ ? ::: The longest branch shrinks by a constant factor $9/10$ each step, so height $= lo g_{10/9} n$ , which differs from $lo g_{2} n$ only by a constant. Height stays $Θ (lo g n)$ . When are $z_{i}$ and $z_{j}$ compared? ::: Exactly when the first pivot chosen from ${z_{i}, \dots, z_{j}}$ is $z_{i}$ or $z_{j}$ ; probability $\frac{2}{j - i + 1}$ . What makes the tree $n$ tall in the worst case? ::: A pivot that is always the min (or max) peels off only one element, so each segment shrinks by $1$ , not by half.

See also: Merge Sort (splits trivially, works while merging — the mirror image), Quickselect (same partition, recurse on one side, expected $O (n)$ ), Dutch National Flag Problem (3-way split for duplicates), Binary Search (the other place $lo g n$ height shows up).