Quicksort & PARTITION
In-place divide-and-conquer with a trivial combine; the four-region PARTITION invariant; best/avg Θ(n lg n) but worst Θ(n²) on sorted input.
All the work is in the divide
Quicksort is divide-and-conquer where partitioning is everything and the combine step does *nothing*. To sort $A[p..r]$: PARTITION picks a pivot, rearranges so everything $\le$ pivot is on its left and everything $>$ pivot is on its right, and returns the pivot's final index $q$. Then recurse on $A[p..q-1]$ and $A[q+1..r]$. Because the pivot is already in its final sorted slot and each side is sorted in place, no merge is needed — that is why quicksort sorts in place.
PARTITION and its four-region invariant
Lomuto's PARTITION takes $x = A[r]$ as the pivot and scans $j$ from $p$ to $r-1$, maintaining four regions:
- $A[p..i]$ — known $\le x$ (the low side), - $A[i+1..j-1]$ — known $> x$ (the high side), - $A[j..r-1]$ — not yet examined, - $A[r] = x$ — the pivot, parked at the end.
When $A[j] \le x$, increment $i$ and swap $A[i]\leftrightarrow A[j]$ (grow the low side); otherwise just advance $j$ (grow the high side). After the loop, swap $A[i+1]\leftrightarrow A[r]$ to drop the pivot between the two sides and return $i+1$. The loop does $O(1)$ work per element, so PARTITION is $\Theta(n)$.
When it wins and when it loses
- Best case: every split is balanced (size $\le n/2$ each). $T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)$. - Worst case: every split is $0$ vs $n-1$. $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$. - Average case: $\Theta(n\lg n)$ — and remarkably, *any* constant-ratio split (even 9-to-1) still gives $\Theta(n\lg n)$, because the recursion tree stays $\Theta(\lg n)$ deep with $\Theta(n)$ work per level.
The worst case is triggered by already-sorted (or reverse-sorted) input when the pivot is always $A[r]$: the pivot is always the max (or min), so one side is always empty. Sorted input — the easy case for insertion sort — is the *worst* case for fixed-pivot quicksort. The next lesson fixes this with randomization.
Worked example
PARTITION on $\langle 2,8,7,1,3,5,6,4\rangle$ with pivot $4$ returns index $3$ and leaves $\langle 2,1,3,4,7,5,6,8\rangle$ — everything left of index 3 is $\le 4$, everything right is $> 4$, and $4$ sits in its final place. Running full quicksort then yields the sorted list. Both runnable exercises reproduce this.