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

Before we start, three words are used constantly below — pin them down once:

True or false — justify

TF — "Quicksort's combine step does real work, like merge sort's merge."

False. Once partition places the pivot between a smaller-left group and a bigger-right group, the two halves are already on the correct sides, so gluing them is free — all the work lives in partitioning.

TF — "Quicksort is a stable sort."

False. Partition swaps far-apart elements, so two equal keys can end up in swapped relative order; that reordering is exactly what breaks stability.

TF — "Quicksort always uses

O (n)

extra memory."

False. It sorts in place; the only extra memory is the recursion stack, which is

O (lo g n)

on average (and

O (n)

in the worst chain if you recurse the wrong side).

TF — "If every pivot splits the array exactly in half, quicksort runs in

Θ (n lo g n)

True. Halving gives recursion depth

lo g_{2} n

, and each depth level scans all

n

elements once, so total work is

n \times lo g_{2} n

TF — "You need exactly-even splits to get

n lo g n

False. Even a fixed lopsided split like

\frac{1}{10}

\frac{9}{10}

keeps depth at

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

, so it is still

Θ (n lo g n)

TF — "Using a random pivot makes the

O (n^{2})

worst case impossible."

False. Bad luck could still pick the minimum every time; what randomization removes is any fixed input that reliably triggers it (the bad case now has probability

\sim 1/ n!

TF — "Median-of-three pivoting guarantees

O (n lo g n)

False. It defeats the sorted-array trap, but an adversary can still construct inputs forcing

Θ (n^{2})

; only introsort (switching to heapsort at deep recursion) gives a true guarantee.

TF — "Hoare partition returns the pivot's final sorted index, just like Lomuto."

False. Hoare returns a boundary

j

splitting the array into "all

\leq

" and "all

\geq

" halves; the pivot is not guaranteed to sit at

j

TF — "Duplicate values never affect quicksort's running time."

False. With Lomuto, an all-equal array puts everything on one side, degenerating to the

O (n^{2})

chain; 3-way (Dutch flag) partitioning fixes this.

TF — "The expected number of comparisons is about

2 n ln n

True. Summing the pairwise probabilities

\frac{2}{j - i + 1}

gives

E [comparisons] \leq 2 n H_{n} \approx 2 n ln n \approx 1.39 n lo g_{2} n

Spot the error

Error — "I ran Hoare partition and recursed with quicksort(lo, q-1) and quicksort(q+1, hi)."

Wrong: that q-1/q+1 split is for Lomuto (which returns the pivot's index). Hoare returns a boundary, so use quicksort(lo, j) and quicksort(j+1, hi) — otherwise you drop an element or loop forever.

Error — "In Lomuto I set pivot = A[hi] but then never swap the pivot at the end; I just return i+1."

Wrong: without the final swap A[i+1], A[hi] the pivot stays parked at hi and index i+1 holds some

\geq

-pivot element, so the pivot is not placed and the partition is broken.

Error — "In Lomuto's condition I wrote if A[j] <= pivot to be safe with duplicates."

Using

\leq

moves every equal element into the left zone, so on an all-equal array all

n - 1

elements pile on one side — that is the

O (n^{2})

degeneration, the opposite of safe.

Error — "In Hoare I did while A[i] <= pivot and while A[j] >= pivot to skip equals."

Wrong: with

\leq

\geq

the pointers can run past the array bounds and equal elements never stop them, breaking the loop; the correct strict conditions are A[i] < pivot and A[j] > pivot.

Error — "I picked pivot = A[lo] for Hoare but returned i instead of j."

Wrong: Hoare's valid boundary is j; returning i when the pointers cross can point to an element belonging to the right half and produce an unbalanced or incorrect split.

Error — "My quicksort recurses on the larger side first to save stack space."

Backwards: recursing on the smaller side first (and tail-looping the larger) is what caps stack depth at

O (lo g n)

; doing the larger side first can grow the stack to

O (n)

Why questions

Why — "Why is the pivot in its final position after partition, needing no further moves?"

Because every smaller element is to its left and every larger to its right, so in the fully sorted array the pivot must occupy exactly that boundary index — nothing can push it.

Why — "Why does Hoare do fewer swaps than Lomuto on random data?"

Hoare only swaps a genuinely out-of-place pair (a big-on-left with a small-on-right), whereas Lomuto swaps for every element it finds below the pivot, so Hoare skips the already-correct ones (~3× fewer swaps).

Why — "Why are two elements

z_{i}, z_{j}

compared iff one of them is the first pivot chosen from the range between them?"

If something strictly between them is chosen first, that pivot splits them into different subarrays and they never meet again; only if one endpoint is picked first do they get directly compared.

Why — "Why does the probability of comparing

z_{i}

and

z_{j}

equal

\frac{2}{j - i + 1}

The range

{z_{i}, \dots, z_{j}}

has

j - i + 1

equally-likely-first pivots, and exactly

2

of them (the two endpoints) cause a comparison, giving

2/ (j - i + 1)

Why — "Why does the sorted-array-plus-last-pivot case blow up to

O (n^{2})

The last element is already the maximum, so partition peels off just one element per call, turning the recursion into a length-

n

chain with work

n + (n - 1) + \dots = Θ (n^{2})

Why — "Why is a constant-fraction split (not perfect halves) still

O (n lo g n)

Depth is set by the longest root-to-leaf path; if size shrinks by a fixed factor each step, that length is

lo g_{1/ fraction} n = Θ (lo g n)

, and each level still costs

\leq c n

Why — "Why does 3-way (Dutch flag) partitioning help with heavy duplicates?"

It groups elements into < = > and never recurses into the equal block, so an all-equal array is solved in one linear pass instead of degenerating to

Θ (n^{2})

Edge cases

Edge — "What does quicksort do on an array of size 0 or 1?"

Nothing — it hits the base case (

\leq 1

element is already sorted) and returns immediately without partitioning.

Edge — "What happens on an array where every element is equal, using Lomuto with strict <?"

No element is < pivot, so i never advances; the pivot lands at lo and one side keeps all

n - 1

elements — the

O (n^{2})

worst case.

Edge — "In Lomuto, where does the pivot go if all other elements are larger than it?"

The if A[j] < pivot test never fires, i stays at lo-1, and the final swap puts the pivot at index lo — correct, since it is the minimum.

Edge — "In Hoare, what if the pivot happens to be the largest element in the subarray?"

The right pointer j walks all the way left until the pointers cross, returning a boundary near lo; the recursion still terminates because at least one element separates, avoiding an infinite loop.

Edge — "Does the do i=i+1 before the test (do-while order) matter in Hoare?"

Yes — advancing before testing guarantees each pointer moves at least once per outer iteration, which is what prevents the two pointers from getting stuck on the same spot and looping forever.

Edge — "What is the recursion depth if you always pick the worst pivot but recurse smaller-side-first?"

The time is still

O (n^{2})

, but the stack depth stays

O (lo g n)

because you only stack the smaller sub-call each time and iterate the larger.

Recall Quick self-test

Hoare recursion split uses which indices? ::: quicksort(lo, j) and quicksort(j+1, hi) — j is a boundary, not the pivot's index. One-line reason quicksort is unstable? ::: Partition swaps distant elements, so equal keys can flip relative order. Expected comparison count in one expression? ::: About $2 n ln n \approx 1.39 n lo g_{2} n$ .