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

Before you can read a line of that parent note, you need a vocabulary. Below is every symbol and idea it silently assumes, each built from nothing, in an order where each rung of the ladder rests on the one below it. If a term already makes total sense to you, skim — but the [!recall] checklist at the bottom is the real test.

1. An array and its indices

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

The picture: look at the strip above. The teal number under each box is its index $k$ ; the plum number inside is the value $A [k]$ . So here $A [3]$ is the fourth box.

Why the topic needs it: every pointer in Lomuto and Hoare (i, j, lo, hi, q) is just an index — a finger pointing at one box. If "index" is fuzzy, all the pointer-chasing is noise.

2. Subarray and the range $[lo, hi]$

The picture: imagine two brackets you can slide inward around any chunk of the row. Everything between them is the subarray you are currently working on.

Why the topic needs it: quicksort is recursive — it calls itself on smaller pieces. Each call says "sort just this slice, from lo to hi." Without a way to name a slice, recursion cannot even be stated.

3. Swap — the one physical move

The picture: two boxes trade the numbers inside them, like two people swapping seats. The indices stay put; only the values travel.

Why the topic needs it: quicksort is in-place — it never builds a second array, it only rearranges the boxes it already has. The only tool for rearranging is swap. Every partition routine is a sequence of swaps.

4. The pivot $p$ and "partition"

The picture: three coloured zones. The orange left zone holds everything $< p$ ; the single teal box is the pivot in its home $q$ ; the plum right zone holds everything $> p$ . The zones are unsorted within themselves — that is what recursion fixes next.

Why the topic needs it: this is the whole engine. Once $p$ is at $q$ , the problem splits into two smaller, independent problems (left zone, right zone) that never interact again. " $q$ " is exactly the return value of Lomuto's partition.

5. Comparisons: $<$ , $>$ , $\geq$ , $=$

Why the topic needs it: partition decides which zone a value belongs to by comparing it to the pivot. The exact choice of $<$ vs $\geq$ is what the loop invariant pins down (e.g. " $A [lo .. i] < p$ " uses strict less-than). Getting these boundaries right is the difference between correct code and an infinite loop — especially with duplicate (equal) values, which is why the parent note flags equal elements as dangerous.

6. Pointers `i`, `j` and their invariants

The picture: j (plum arrow) sweeps left-to-right inspecting values; i (orange arrow) lags behind, sitting at the last box already known to be $< p$ . Every time j finds a small value, i steps forward and swaps it in.

Why the topic needs it: the parent's proof of correctness is its invariant ( $A [lo .. i] < p$ , etc.). An invariant is how you trust code without tracing every case: if it holds at the start, and each step preserves it, then it holds at the end — and the end statement is exactly "the array is partitioned." This is the logical backbone of both Lomuto and Hoare.

7. Recursion and the recursion tree

The picture: the balanced tree (left) halves each time → short and bushy, depth $\approx lo g_{2} n$ . The lopsided chain (right) peels one element per call → depth $\approx n$ . Same algorithm, wildly different shapes depending on pivot luck.

Why the topic needs it: the entire complexity story lives in this tree. Each level does $Θ (n)$ work (one partition pass over its boxes). So total work = work-per-level × depth. Bushy tree → $n \times lo g n$ . Chain → $n \times n$ . That is literally where $O (n lo g n)$ and the $O (n^{2})$ worst case come from.

8. Big-O and $Θ$ — the size labels

Why the topic needs it: the whole reason quicksort matters is its speed label. "Expected $Θ (n lo g n)$ , worst $Θ (n^{2})$ " is a one-line summary of the recursion-tree analysis. Without these labels you cannot compare quicksort to Merge Sort or Heap Sort.

9. Logarithm $lo g_{2} n$ — the depth of a bushy tree

The picture: each level of a balanced recursion tree cuts the slice in half. The number of levels until size $1$ is the number of halvings — that is $lo g_{2} n$ . That's why a balanced quicksort tree has depth $lo g_{2} n$ .

Why the topic needs it: the "log" in $n lo g n$ is this halving count. It is why doubling the array only adds one level of work, not double the work.

10. Sum $\sum$ and the harmonic number $H_{n}$

Why the topic needs it: the parent's expected-comparison count is $2 n H_{n} \approx 2 n ln n$ . If $\sum$ and $H_{n}$ are unfamiliar, the elegant " $Pr = \frac{2}{j - i + 1}$ " derivation is unreadable. You do not need to derive $H_{n} \approx ln n$ here — just recognise that this friendly sum is what produces the $lo g$ in the average case.

Recall Why does a sum of

$1/ k$ give a logarithm? Because adding up $1/ k$ from $1$ to $n$ is close to the area under the curve $1/ x$ , and that area is exactly $ln n$ . (Full detail lives with the Master Theorem toolkit — here just trust the shape.)

How the foundations feed the topic

Equipment checklist

Test yourself — cover the right side and answer out loud.

What does

A [k]

mean, and why do indices start at 0?

The value in box number

k

; counting from 0 means an

n

-box array uses indices

0.. n - 1

How many boxes are in the slice

A [lo .. hi]

hi - lo + 1

(both ends included).

Why does quicksort use swap instead of inserting?

Swap touches exactly two boxes (

O (1)

); it keeps the algorithm in-place and cheap.

After partitioning, where is the pivot

p

In its final sorted position

q

— everything left is smaller, everything right is bigger.

What is a loop invariant?

A statement true at the top of the loop every pass; it proves the partition is correct at the end.

Why does each level of the recursion tree cost

Θ (n)

One partition pass at each level scans all the boxes on that level, totalling

n

What question does

lo g_{2} n

answer?

How many times you halve

n

to reach 1 — i.e. the depth of a balanced tree.

Difference between

O (f)

and

Θ (f)

O

is an upper bound (at most);

Θ

is tight (grows exactly like

f

What is

H_{n}

and roughly how big is it?

H_{n} = 1 + 1/2 + \dots + 1/ n \approx ln n

; it produces the log in the average-case count.

Ready? If every line above felt solid, jump to the parent note and read the Lomuto trace — every pointer will now be a familiar finger on a familiar box.