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

The scenario matrix

Every quicksort question is really one of these cells. The examples below are labelled with the cell they cover.

#	Cell class	What makes it special	Which partition breaks / shines
C1	Random / generic array	typical case, splits are unbalanced-ish	Lomuto & Hoare both fine, $O (n lo g n)$
C2	Already sorted (ascending)	last-element pivot is always the max	Lomuto → $O (n^{2})$ worst case
C3	Reverse sorted	last-element pivot is always the min	Lomuto → $O (n^{2})$ worst case
C4	All elements equal	every comparison is a "tie"	Lomuto → $O (n^{2})$ ; 3-way → $O (n)$
C5	Degenerate size ( $n = 0, 1, 2$ )	base case / smallest real work	tests the recursion boundary
C6	Hoare vs Lomuto same input	Hoare returns a boundary, not pivot index	shows the recursion-index trap
C7	Median-of-three defense	sorted input made harmless	shows why the trick works
C8	Word problem (leaderboard)	real numbers, real question	expected comparisons formula
C9	Exam twist (count comparisons)	uses $2 n H_{n}$ and the split recurrence	the "derive it" cell

C1 — Random array (Lomuto, the typical case)

Worked example Partition

[4, 1, 7, 3, 6, 2, 5] with Lomuto (pivot = last = 5) Forecast: guess where the 5 ends up — how many elements are smaller than 5? Write your guess before scrolling.

We use the Lomuto rule from the parent: i marks the last index of the "< pivot" zone; j scans; each time A[j] < 5 we do i=i+1; swap A[i],A[j].

Setup. pivot=5, i=-1, zone empty. Why this step? i=-1 means "the less-than zone has no elements yet"; the first small element will land at index 0.
j=0, A[0]=4 < 5 → i=0, swap A[0],A[0] → [4] 1 7 3 6 2 5. Why? 4 belongs left; it's already there, so the swap is a no-op but still grows the zone.
j=1, A[1]=1 < 5 → i=1, swap A[1],A[1] → [4 1] 7 3 6 2 5.
j=2, A[2]=7 ≥ 5 → zone unchanged [4 1] 7 3 6 2 5. Why? 7 is on the correct (right) side; leave it, keep scanning.
j=3, A[3]=3 < 5 → i=2, swap A2,A3 → [4 1 3] 7 6 2 5. Why? The 7 that was blocking the zone gets kicked out to where the 3 was — this is how a big element migrates right.
j=4, A[4]=6 ≥ 5 → unchanged [4 1 3] 7 6 2 5.
j=5, A[5]=2 < 5 → i=3, swap A3,A5 → [4 1 3 2] 6 7 5.
Final swap. Put pivot after the zone: swap A[i+1]=A4 with A[hi]=A6 → [4 1 3 2] 5 7 6. Return q = i+1 = 4.

Verify: everything left of index 4 is {4,1,3,2} all < 5 ✓, everything right is {7,6} all > 5 ✓. Number smaller than 5 was four, so the pivot lands at index 4 — matches the forecast if you counted right.

C2 — Already sorted array (Lomuto worst case)

Worked example Trace the

number of partition passes for [1, 2, 3, 4] with Lomuto (last-element pivot) Forecast: how many total comparisons? Guess: is it closer to $n lo g n \approx 8$ or $n^{2} \approx 16$ ?

Call on [1,2,3,4], pivot=4. Every element (1,2,3) is < 4, so all three grow the zone. Final swap of 4 with itself. Pivot at index 3. Comparisons: 3. Why this step? The pivot is the maximum, so the "right" part is empty and the "left" part has $n - 1 = 3$ elements. That is the definition of an unbalanced peel.
Recurse left on [1,2,3], pivot=3. Comparisons: 2. Pivot at index 2, left part size 2.
Recurse left on [1,2], pivot=2. Comparisons: 1. Left size 1 → base case.
Recurse on [1]. Size 1, base case, 0 comparisons.

Total comparisons $= 3 + 2 + 1 + 0 = 6 = (2 4)$ .

Verify: the general formula for the fully-unbalanced case is $\sum_{k = 1}^{n - 1} k = \frac{n ( n - 1 )}{2}$ . For $n = 4$ : $\frac{4 \cdot 3}{2} = 6$ ✓. This is $Θ (n^{2})$ , not $Θ (n lo g n)$ — the sorted-array gotcha is real. (Cell C2.)

C3 — Reverse sorted (still worst case, opposite peel)

C4 — All elements equal (the duplicate trap)

Worked example Partition

[5, 5, 5, 5] with Lomuto vs 3-way (Dutch National Flag) Forecast: with plain Lomuto and pivot=5, how many elements satisfy A[j] < 5? Guess the left-part size.

Lomuto path:

Pivot = 5. Comparison test is strict A[j] < 5. Since every element equals 5, no comparison is ever true. Why this step? The strict < means equal elements are treated as "not smaller", so they all stay right — i never advances.
Zone empty, final swap puts pivot at index 0. Left size 0, right size $n - 1 = 3$ . Why? Same one-element peel as the sorted case → $Θ (n^{2})$ . All-equal is the sneakiest worst case because it looks "easy".

3-way path (see Dutch National Flag Problem): 3. A 3-way partition groups the array into < 5, = 5, > 5. Here the whole array is the = 5 block. Why? The equal block is placed and never recursed into — it's already sorted (all identical). 4. Left < 5 and right > 5 are both empty. Recursion ends immediately.

Verify: Lomuto comparisons $= \frac{n ( n - 1 )}{2} = \frac{4 \cdot 3}{2} = 6$ and depth $n = 4$ → $O (n^{2})$ . 3-way does one linear pass of $n = 4$ comparisons and stops → $O (n)$ . For all-equal input 3-way is $4$ vs Lomuto's $6$ comparisons here, and the gap explodes as $n$ grows. (Cell C4.)

C5 — Degenerate sizes (the base cases)

Worked example What does quicksort do on

[], [9], and [8, 2]? Forecast: how many of these need any partition work at all?

[] (size 0). lo > hi, so the recursion returns immediately. Why this step? An empty range is sorted by definition; touching it would be a bug (out-of-bounds).
[9] (size 1). lo == hi, base case, return. 0 comparisons. Why? A single element is trivially in sorted order — nothing to compare it against.
[8, 2] (size 2), Lomuto pivot = A[hi] = 2.
- j=0: A[0]=8 < 2? No. Zone stays empty.
- Final swap: swap A[0]=8 with A[1]=2 → [2, 8]. Pivot at index 0. Why? Size-2 is the smallest array that does real work: exactly 1 comparison and possibly 1 swap.

Verify: result [2,8] is sorted ✓. Comparison counts: 0, 0, 1. The base case size ≤ 1 correctly catches both [] and [9] without indexing errors. (Cell C5.)

C6 — Hoare vs Lomuto on the same input (the index trap)

Worked example Partition

[3, 8, 2, 5, 1, 4, 7, 6] with Hoare (pivot = first = 3) and read off the recursion indices Forecast: Lomuto would return the pivot's final index. Hoare returns a boundary j. Guess: will A[j] equal the pivot 3?

Hoare rule: i starts at lo-1, j at hi+1. Repeat: advance i while A[i] < pivot; retreat j while A[j] > pivot; if i >= j return j; else swap.

Round 1. i: from -1, A[0]=3 not < 3, stop at i=0. j: from 8, A[7]=6>3, A[6]=7>3, A[5]=4>3, A[4]=1 not >3, stop at j=4. i=0 < j=4 → swap A[0],A[4]: [1, 8, 2, 5, 3, 4, 7, 6]. Why this step? Left pointer found a ≥3 on the wrong side (the 3 itself), right pointer found a ≤3 on the wrong side (the 1). Swapping fixes two elements at once — that's Hoare's efficiency.
Round 2. i: A[1]=8 not <3, stop at i=1. j: A[3]=5>3, A[2]=2 not >3, stop at j=2. i=1 < j=2 → swap A[1],A[2]: [1, 2, 8, 5, 3, 4, 7, 6].
Round 3. i: A[2]=8 not <3, stop at i=2. j: A[2]=8>3, A[1]=2 not >3, stop at j=1. Now i=2 >= j=1 → return j=1. Why? Pointers crossed. Everything in [lo..1]={1,2} is ≤ everything in [2..hi]={8,5,3,4,7,6}.
Recurse the Hoare way: quicksort(lo, j) = quicksort(0,1) and quicksort(j+1, hi) = quicksort(2,7). Note: j, not j-1/j+1. Why? The pivot 3 is at index 4, not at j=1. If you wrongly used quicksort(0, j-1)=quicksort(0,0) and quicksort(j+1,7)=quicksort(2,7) you would drop index 1 from sorting — the classic bug in the parent's steel-man.

Verify: boundary property — max([1,2]) = 2 ≤ min([8,5,3,4,7,6]) = 3 ✓. And A[j]=A[1]=2 ≠ 3=pivot, confirming Hoare's boundary is NOT the pivot's home. (Cell C6.)

C7 — Median-of-three defense on sorted input

Worked example Show median-of-three turns the C2 disaster into a balanced split for

[1, 2, 3, 4, 5, 6, 7] Forecast: last-element pivot (7) gives a size-6/size-0 split. What split does median-of-three give?

Look at three positions: A[lo]=A[0]=1, A[mid]=A[3]=4, A[hi]=A[6]=7. Why this step? Instead of trusting one element, we sample three and take their median — the middle value is far likelier to split evenly.
Median of {1, 4, 7} is 4. Use 4 as the pivot. Why? On a sorted array, A[mid] is literally the true median, so the split is perfect.
Partition around 4: left {1,2,3} (size 3), pivot 4, right {5,6,7} (size 3). Why? A 3/3 split instead of 6/0 — recursion depth drops from $n$ toward $lo g_{2} n$ .

Verify: depth for a perfect split satisfies $T (n) = 2 T (n /2) + c n = Θ (n lo g n)$ (Master Theorem, from the parent). For $n = 7$ : split sizes 3 and 3 (pivot removed) are equal → best possible. Compare C2's 6/0 split. (Cell C7.) Note: median-of-three still has a theoretical $O (n^{2})$ ; for a guarantee use Introsort.

C8 — Word problem (expected comparisons)

Worked example A leaderboard has

1000 distinct scores in random order. Estimate the expected number of comparisons randomized quicksort makes to sort them. Forecast: will it be closer to $100 0^{2} = 1 0^{6}$ or to about $1000 \times 10 = 1 0^{4}$ ?

Use the parent's formula $E [comparisons] \approx 2 n ln n$ . Why this step? Each pair of scores is compared with probability $\frac{2}{j - i + 1}$ ; summing the indicators gives $2 n H_{n} \approx 2 n ln n$ . This is the whole point of the indicator-variable derivation.
Plug in $n = 1000$ : $ln 1000 \approx 6.9078$ . Why? $ln$ (natural log) appears because $H_{n} = \sum 1/ k \approx ln n$ ; it's not a choice, it's what the harmonic sum equals.
Compute: $2 \times 1000 \times 6.9078 \approx 13816$ . Why? This counts key comparisons, the dominant cost of sorting.

Verify: $2 n ln n = 2000 \times 6.9078 = 13815.5 \dots \approx 13816$ comparisons — that's about $1.4 \times 1 0^{4}$ , four orders of magnitude below the $1 0^{6}$ worst case. Randomization keeps us in $O (n lo g n)$ land. (Cell C8.) A sanity cross-check: $2 n ln n = 1.386 n lo g_{2} n$ , and $lo g_{2} 1000 \approx 9.97$ , so $1.386 \times 1000 \times 9.97 \approx 13818$ ✓ (rounding).

C9 — Exam twist (bound the 9-to-1 split)

Worked example Every pivot splits a subarray into a

$\frac{1}{10}$ part and a $\frac{9}{10}$ part. Prove the recursion depth is still $Θ (lo g n)$ for $n = 100000$ , and give the depth number. Forecast: does a lopsided 90/10 split ruin $n lo g n$ ? Guess yes/no.

The longest path repeatedly takes the bigger $\frac{9}{10}$ piece. Why this step? Worst depth is driven by the slowest-shrinking branch — the $9 n /10$ side.
After $d$ levels the size is $n (\frac{9}{10})^{d}$ . The chain ends when this hits 1: $(\frac{9}{10})^{d} n = 1$ . Why? Once a subarray has 1 element it's a base case — the leaf.
Solve: $d = lo g_{10/9} n = \frac{ln n}{ln ( 10/9 )}$ . Why? Taking logs of both sides converts the exponent into a multiplier — logs answer "how many times do I multiply by $9/10$ to reach 1?"
Plug in $n = 100000$ : $ln (100000) = 11.5129$ , $ln (10/9) = 0.10536$ , so $d \approx 109.3$ .

Verify: $\frac{ln 100000}{ln ( 10/9 )} = \frac{11.5129}{0.10536} \approx 109.3$ . Depth $\approx 109$ levels — a constant ( $\approx 10.5 \times$ ) more than the perfect $lo g_{2} 100000 \approx 16.6$ , and each level still costs $\leq c n$ , so total is $Θ (n lo g n)$ . A lopsided-but-constant-fraction split does not ruin quicksort. (Cell C9.)

Recall Self-test (reveal after guessing)

Lomuto on already-sorted [1,2,3,4] — comparison count? ::: $(2 4) = 6$ , i.e. $Θ (n^{2})$ . Hoare returns index j; which recursion calls do you make? ::: quicksort(lo, j) and quicksort(j+1, hi) — never j-1/j+1. All-equal array with plain Lomuto — best or worst case? ::: Worst, $O (n^{2})$ ; fix with 3-way partitioning. Expected comparisons to sort 1000 distinct items? ::: $\approx 2 n ln n \approx 13816$ . Median-of-three pivot for sorted [1..7]? ::: median of {1,4,7} = 4 → perfect 3/3 split.

See also: Merge Sort, Heap Sort, Quickselect, Randomized Algorithms, Master Theorem, Binary Search.