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

1. The skeleton

WHAT distinguishes quicksort from merge sort: merge sort splits trivially (middle index) and does work while merging; quicksort does work while splitting and merges trivially. The pivot choice is the algorithm.

2. Lomuto partition (the easy one)

Formula Lomuto pseudocode + invariant

partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1                  # i = last index of "< pivot" zone
    for j in lo .. hi-1:
        if A[j] < pivot:
            i = i + 1
            swap A[i], A[j]
    swap A[i+1], A[hi]          # put pivot after the zone
    return i + 1                # pivot's final index

Loop invariant (before iteration j):

$A[\text{lo}..i] <$ pivot
$A[i+1..j-1] \ge$ pivot
$A[\text{hi}]$ = pivot

When the loop ends, $A[i+1..\text{hi}-1]\ge$ pivot, so swapping pivot to index $i+1$ places it correctly.

Worked example Lomuto trace on

[3, 7, 8, 5, 2, 1, 9, 5_pivot] (pivot = 5)

step (j)	A[j]	<5?	i	array (zone in [])
start	–	–	-1	[ ]3 7 8 5 2 1 9 5
0	3	yes	0	[3] 7 8 5 2 1 9 5
1	7	no	0	[3] 7 8 5 2 1 9 5
2	8	no	0	[3] 7 8 5 2 1 9 5
3	5	no (==)	0	[3] 7 8 5 2 1 9 5
4	2	yes	1	[3 2] 8 5 7 1 9 5
5	1	yes	2	[3 2 1] 5 7 8 9 5
6	9	no	2	[3 2 1] 5 7 8 9 5
final swap	–	–	–	3 2 1 5 7 8 9 5 → pivot at index 3

Why this step? At j=4 (value 2) we grow the zone and swap the 2 leftward — that's how small elements migrate left. The single final swap drops the pivot exactly between the zones.

3. Hoare partition (the efficient original)

Formula Hoare pseudocode

partition(A, lo, hi):
    pivot = A[lo]               # often first element
    i = lo - 1
    j = hi + 1
    while true:
        do i = i+1  while A[i] < pivot
        do j = j-1  while A[j] > pivot
        if i >= j: return j      # NOTE: returns a split point, NOT pivot's final index
        swap A[i], A[j]

Crucial difference: Hoare returns a boundary j such that everything in [lo..j] $\le$ everything in [j+1..hi], but the pivot is not guaranteed at index j. So recursion is quicksort(lo, j) and quicksort(j+1, hi) — note j, not j-1/j+1.

4. Why it averages $O(n\log n)$ — derive it

Derivation (recurrence, balanced case). $T(n) = 2\,T(n/2) + cn$ By the Master Theorem ( $a=2,b=2,f(n)=cn$ , with $n^{\log_b a}=n$ ): the regular case gives $T(n) = \Theta(n\log n).$

Even a 9-to-1 split is fine. Suppose every split is $\frac{1}{10}$ vs $\frac{9}{10}$ : $T(n)=T(n/10)+T(9n/10)+cn.$ The longest root-to-leaf path shrinks by factor $9/10$ each step, so depth $= \log_{10/9} n = \Theta(\log n)$ , and each level costs $\le cn$ → still $\Theta(n\log n)$ .

Average over random pivots — counting comparisons. Let elements in sorted order be $z_1<z_2<\dots<z_n$ . Let indicator $X_{ij}=1$ if $z_i$ and $z_j$ are ever compared.

Formula The expected comparison count

Two elements $z_i,z_j$ are compared iff one of them is the first pivot chosen from the set $\{z_i,\dots,z_j\}$ (size $j-i+1$ ). If anything strictly between them is picked first, they get separated into different subarrays and never meet. $\Pr[X_{ij}=1]=\frac{2}{\,j-i+1\,}$ $E[\text{comparisons}]=\sum_{i<j}\frac{2}{j-i+1}=\sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k}\le 2\sum_{i=1}^{n}H_n = 2nH_n$ Since $H_n=\sum_{k=1}^n \frac1k \approx \ln n$ , $E[\text{comparisons}]\approx 2n\ln n \approx 1.39\,n\log_2 n = \Theta(n\log n).$

Why this step? The "first pivot from the gap" argument turns a messy recursion into clean indicator-variable probabilities — that's the 80/20 insight worth memorizing.

5. Worst case $O(n^2)$ — and how to dodge it

$T(n)=T(n-1)+cn \implies T(n)=\Theta(n^2).$

This happens with Lomuto + last-element pivot on an already sorted (or reverse-sorted) array — the classic gotcha.

Formula Pivot strategies (defenses)

Strategy	Idea	Worst case
First/last element	simple	$O(n^2)$ on sorted input
Random pivot	pick uniformly random index, swap to end	Expected $O(n\log n)$ ; adversary can't force bad input
Median-of-three	median of `A[lo], A[mid], A[hi]`	Kills sorted-array worst case; still $O(n^2)$ theoretically
Introsort	quicksort, switch to heapsort when recursion depth $>2\log n$	Guaranteed $O(n\log n)$

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

6. Properties summary

7. Active recall

Recall Quick self-test (cover the answers)

Why does Lomuto place the pivot correctly at the end? → invariant guarantees $A[i+1..hi-1]\ge$ pivot, so pivot belongs at $i+1$ .
What does Hoare's return value mean? → a split boundary, not the pivot's index.
Probability two elements are compared? → $2/(j-i+1)$ .
When is the worst case triggered with last-element pivot? → sorted / reverse-sorted input.

What is the core idea of quicksort?

Pick a pivot, partition so smaller elements go left and larger go right (pivot lands in final position), then recurse on both sides.

What does Lomuto partition return?

The final sorted index of the pivot (i+1).

What does Hoare partition return?

A partition boundary j; the pivot is NOT guaranteed to be at j, so recurse on (lo,j) and (j+1,hi).

Why does Hoare do fewer swaps than Lomuto?

It only swaps genuinely out-of-place pairs from two converging pointers, instead of swapping every small element it scans.

What is quicksort's average time complexity and why?

Θ(n log n); balanced (constant-fraction) splits give O(log n) depth with O(n) work per level.

What is the probability that sorted elements z_i and z_j are ever compared?

2/(j−i+1) — they compare iff one of them is the first pivot chosen from {z_i..z_j}.

What is the expected comparison count of randomized quicksort?

About 2n·H_n ≈ 1.39 n log₂ n = Θ(n log n).

When does quicksort hit O(n²)?

When pivots are consistently the min/max, e.g. last-element pivot on sorted/reverse-sorted input, peeling off one element per call.

How does random pivot help, and what does it NOT fix?

It removes any fixed worst-case input (expected n log n), but worst case is still O(n²) — just astronomically unlikely.

What is median-of-three?

Choose the median of A[lo], A[mid], A[hi] as pivot to avoid the sorted-array worst case.

What is introsort?

Quicksort that switches to heapsort once recursion depth exceeds ~2 log n, guaranteeing O(n log n).

Is quicksort stable?

No — swaps can reorder equal keys.

How do you keep stack space O(log n)?

Recurse on the smaller partition first and loop (tail-call) on the larger.

How to handle many duplicate keys efficiently?

3-way (Dutch national flag) partition into <, =, > and skip the equal block.

Recall Feynman: explain to a 12-year-old

Imagine a messy line of kids by height and you want them sorted. You grab one kid (the pivot) and say: "everyone shorter than me, stand on my left; taller, on my right." Now that kid is exactly where they belong — they don't move again. You repeat the same game separately on the left group and the right group. Keep doing it until each tiny group has one kid. The whole line is sorted! If you accidentally always pick the shortest kid as pivot, only one kid gets placed each round and it takes forever — that's the slow case. Picking a random kid almost always splits the line nicely.

Connections

Merge Sort — also divide & conquer, but stable and guaranteed $n\log n$ (work in merge, not split).
Heap Sort — used inside Introsort as the $O(n\log n)$ fallback.
Master Theorem — solves the $T(n)=2T(n/2)+cn$ recurrence.
Dutch National Flag Problem — 3-way partition for duplicate keys.
Randomized Algorithms — the random-pivot expectation argument.
Quickselect — same partition, used to find the $k$ -th smallest in expected $O(n)$ .
Binary Search — sibling "divide" idea on already-sorted data.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Quicksort ka core idea bahut simple hai: ek element ko pivot chuno, fir array ko aise rearrange karo ki pivot se chote saare left mein aur bade saare right mein chale jaayein. Is ek partition ke baad pivot apni final sorted position par pahunch jaata hai — wo dobara kabhi move nahi karega. Ab left part aur right part do alag chote problems ban gaye, unpe wahi cheez recursively repeat karo. Saara kaam partition step mein hota hai, "combine" free hai kyunki dono halves apni sahi side par already hain.

Do famous partition styles hain. Lomuto simple hai: last element pivot, ek boundary pointer i jo "chote zone" ka end mark karta hai, aur jab bhi koi chota element mile use zone mein swap kar lo. Ye return karta hai pivot ka final index. Hoare zyada efficient hai: do pointers ek dusre ki taraf chalte hain, galat side wale pair swap karte hain — kam swaps lagte hain. Lekin yaad rakho, Hoare ka return ek boundary hai, pivot ka index nahi — isliye recursion (lo, j) aur (j+1, hi) par hota hai, q-1/q+1 par nahi. Ye galti bahut common hai.

Complexity ka funda: agar pivot har baar array ko aadhe-aadhe mein todta hai to tree ki depth log n hoti hai aur har level O(n) kaam — total n log n. Average mein random pivot ke saath bhi yahi nikalta hai (probability argument: do elements tabhi compare hote hain jab unke beech ka koi pehle pivot na bane → 2/(j-i+1)). Worst case n^2 tab aata hai jab pivot hamesha sabse chota/bada nikle — jaise already sorted array par last-element pivot. Iska fix: random pivot, median-of-three, ya guarantee ke liye introsort (depth zyada ho to heapsort par switch). Duplicates bahut ho to 3-way (Dutch flag) partition use karo. Bas itna samajh lo to quicksort poora clear hai!

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

1. The skeleton

2. Lomuto partition (the easy one)

3. Hoare partition (the efficient original)

4. Why it averages $O(n\log n)$ — derive it

5. Worst case $O(n^2)$ — and how to dodge it

6. Properties summary

7. Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Sorting & Searching

Connections