--- title: Quicksort module: Divide & Conquer moduleNumber: 2 lessonNumber: 2 order: 202 summary: | Quicksort sorts in place by partitioning around a pivot and recursing on each side. We give Lomuto and Hoare partitioning with a correctness invariant, see why a bad pivot costs $\Theta(n^2)$ while a balanced one gives $\Theta(n\log n)$, and prove that randomizing the pivot makes the expected cost $\Theta(n\log n)$ on every input. topics: [Comparison Sorting, Probabilistic Analysis] sources: - book: CLRS ref: "Ch. 7 — Quicksort" - book: Skiena ref: "§4 — Sorting and Searching" - book: Erickson ref: "Ch. 1 — Recursion" practice: - title: 'Sort Colors' slug: sort-colors difficulty: Medium - title: 'Sort an Array' slug: sort-an-array difficulty: Medium - title: 'Kth Largest Element in an Array' slug: kth-largest-element-in-an-array difficulty: Medium - title: 'Top K Frequent Elements' slug: top-k-frequent-elements difficulty: Medium --- [Mergesort](/algorithms/divide-and-conquer/mergesort) does its hard work in the **combine** step: splitting is trivial, merging is where the sorting happens. $\textsc{Quicksort}$ flips this around. It does its hard work in the **divide** step, partitioning the array so that everything small comes before everything large, after which the combine step is _empty_. Sort the two parts in place and the whole array is sorted, with no merging required.[^erickson-qs] ## The paradigm applied To sort $A[p..r]$: - **Divide.** Choose a **pivot** element and _partition_ $A[p..r]$ into two regions: a left part whose elements are all $\le$ the pivot, and a right part whose elements are all $\ge$ the pivot, with the pivot itself in between at some index $q$. - **Conquer.** Recursively sort $A[p..q-1]$ and $A[q+1..r]$. - **Combine.** Nothing to do: the subarrays are already in place and in order relative to each other. ```algorithm caption: $\textsc{Quicksort}(A, p, r)$ — sort $A[p..r]$ in place number: 1 if $p < r$ then $q \gets$ call $\textsc{Partition}(A, p, r)$ // pivot at final index q call $\textsc{Quicksort}(A, p, q - 1)$ // everything $\le$ pivot call $\textsc{Quicksort}(A, q + 1, r)$ // everything $\ge$ pivot ``` Everything hinges on $\textsc{Partition}$. ### Partitioning around a pivot Partition _rearranges an array around a pivot_ $x$ so that it falls into three contiguous regions: everything less than the pivot, then the pivot itself sitting at its final sorted index $q$, then everything greater. Sorting $A[p..r]$ around a chosen pivot value $x$ rearranges it into $$ % caption: Partition splits the array into elements less than the pivot, the pivot at % index $q$, then greater elements. \begin{tikzpicture}[>=Stealth] \definecolor{acc}{HTML}{2348F2} % the three regions \draw[fill=acc!8] (0,0) rectangle (3.4,0.8); \draw[fill=acc!25, draw=acc, very thick] (3.4,0) rectangle (4.4,0.8); \draw[fill=red!8] (4.4,0) rectangle (8.0,0.8); % region labels \node at (1.7,0.4) {$<\,x$}; \node at (3.9,0.4) {$x$}; \node at (6.2,0.4) {$>\,x$}; % index brackets underneath \draw[<->] (0,-0.25) -- (3.4,-0.25) node[midway,below] {\footnotesize A[p..q-1]}; \draw[->] (3.9,-0.25) -- (3.9,-0.55) node[below] {\footnotesize $q$}; \draw[<->] (4.4,-0.25) -- (8.0,-0.25) node[midway,below] {\footnotesize A[q+1..r]}; % endpoints \node[above] at (0,0.8) {\footnotesize $p$}; \node[above] at (8.0,0.8) {\footnotesize $r$}; \node[above] at (3.9,0.85) {\footnotesize \texttt{pivot} at $q$}; \end{tikzpicture} $$ No element to the left of $q$ exceeds the pivot, and none to the right is smaller, so the pivot is _already in its final position_. The two recursive sorts never have to look across the boundary at $q$, which is why the combine step vanishes. All of quicksort's work is in making this split, and making it _balanced_. ## Lomuto partition The simplest scheme, due to Lomuto, takes the last element $A[r]$ as the pivot and sweeps an index $j$ across the array, maintaining a boundary $i$ between the elements known to be $\le$ the pivot and those known to be $>$ it.[^clrs-lomuto] ```algorithm caption: $\textsc{Partition}(A, p, r)$ — Lomuto scheme, pivot $= A[r]$ number: 2 $x \gets A[r]$ // the pivot $i \gets p - 1$ // end of $\le x$ region for $j \gets p$ to $r - 1$ do if $A[j] \le x$ then $i \gets i + 1$ exchange $A[i]$ with $A[j]$ exchange $A[i + 1]$ with $A[r]$ // pivot into its slot return $i + 1$ ``` ### Correctness of partition Partition is correct by a four-region loop invariant. > **Invariant (Four-region partition invariant).** At the start of each > iteration of the **for** loop, for any array index $k$: > - if $p \le k \le i$ then $A[k] \le x$; > - if $i + 1 \le k \le j - 1$ then $A[k] > x$; > - $A[r] = x$. > > In words: everything up to $i$ is small, everything from $i+1$ to $j-1$ is > large, the slice from $j$ onward is unexamined, and the pivot waits at the end. > **Proof.** By initialization, maintenance, termination. > - **Initialization.** Before the first iteration $i = p - 1$ and $j = p$, so > both regions (1) and (2) are empty. The invariant holds vacuously, and > $A[r] = x$. > - **Maintenance.** If $A[j] > x$, only $j$ advances, extending the "large" > region (2), which stays valid. If $A[j] \le x$, we increment $i$ and swap $A[i]$ > with $A[j]$: the newly small element joins region (1), and the large element > that was at $A[i]$ moves to the back of region (2). Both regions stay correct. > - **Termination.** The loop ends with $j = r$. Regions (1) and (2) together > cover $A[p..r-1]$. The final swap places the pivot at index $i+1$, with all > smaller elements to its left and all larger to its right, satisfying the > postcondition, and $i+1$ is the pivot's final position $q$. $\qed$ Partition does $\Theta(n)$ comparisons on $n = r - p + 1$ elements. A snapshot of the sweep makes the four regions concrete. On $A = \langle 2,8,7,1,3,5,6,4\rangle$ with pivot $x = A[r] = 4$, just after the scan reaches $j = 5$ the boundary $i$ has collected the small elements on the left, the large ones trail behind, and the rest is still unexamined: $$ % caption: Lomuto sweep on $A=\langle 2,8,7,1,3,5,6,4\rangle$ at $j=5$: the $\le x$ region % (boundary $i$) precedes the $> x$ region, with pivot $x=4$ parked at the end. \begin{tikzpicture}[font=\small, >={Stealth[round]}, cell/.style={draw, minimum width=8mm, minimum height=8mm, font=\small}] \definecolor{acc}{HTML}{2348F2} \foreach \v/\x in {2/0,1/1,3/2} \node[cell, fill=acc!14] at (\x,0) {$\v$}; \foreach \v/\x in {8/3,7/4} \node[cell, fill=black!8] at (\x,0) {$\v$}; \foreach \v/\x in {5/5,6/6} \node[cell] at (\x,0) {$\v$}; \node[cell, fill=acc!35] at (7,0) {$4$}; \draw[acc] (-0.4,0.62) -- (2.4,0.62) node[midway, above=2pt, font=\scriptsize] {$\le x$}; \draw[black] (2.6,0.62) -- (4.4,0.62) node[midway, above=2pt, font=\scriptsize] {$> x$}; \draw[black] (4.6,0.62) -- (6.4,0.62) node[midway, above=2pt, font=\scriptsize] {unexamined}; \node[font=\scriptsize\itshape, acc] at (2,-0.95) {$i$}; \draw[->, acc] (2,-0.7) -- (2,-0.45); \node[font=\scriptsize\itshape] at (5,-0.95) {$j$}; \draw[->] (5,-0.7) -- (5,-0.45); \node[font=\scriptsize\itshape] at (7,-0.95) {pivot}; \end{tikzpicture} $$ The full sweep is worth tracing once, end to end. Each row shows the state at the top of the **for** loop for one value of $j$; swaps that move an element are marked. Recall $x = 4$ and $i$ starts at $p - 1 = 0$. | $j$ | test $A[j] \le 4$ | action | array after | $i$ | | --- | --- | --- | --- | --- | | $1$ | $2 \le 4$: yes | $i \gets 1$; swap $A[1] \leftrightarrow A[1]$ (no-op) | $\langle 2,8,7,1,3,5,6,4\rangle$ | $1$ | | $2$ | $8 \le 4$: no | — | $\langle 2,8,7,1,3,5,6,4\rangle$ | $1$ | | $3$ | $7 \le 4$: no | — | $\langle 2,8,7,1,3,5,6,4\rangle$ | $1$ | | $4$ | $1 \le 4$: yes | $i \gets 2$; swap $A[2] \leftrightarrow A[4]$ | $\langle 2,1,7,8,3,5,6,4\rangle$ | $2$ | | $5$ | $3 \le 4$: yes | $i \gets 3$; swap $A[3] \leftrightarrow A[5]$ | $\langle 2,1,3,8,7,5,6,4\rangle$ | $3$ | | $6$ | $5 \le 4$: no | — | $\langle 2,1,3,8,7,5,6,4\rangle$ | $3$ | | $7$ | $6 \le 4$: no | — | $\langle 2,1,3,8,7,5,6,4\rangle$ | $3$ | | — | loop done | swap $A[i+1] = A[4] \leftrightarrow A[8]$ | $\langle 2,1,3,\mathbf{4},7,5,6,8\rangle$ | — | $\textsc{Partition}$ returns $q = 4$: the pivot $4$ sits at its final sorted index with $\{2,1,3\}$ to its left and $\{7,5,6,8\}$ to its right — neither side sorted yet, but every element on the correct side of the boundary. The recursion takes it from there. Notice how a "yes" row swaps the scanned small element with the _first_ large element (the one just past $i$), leapfrogging the large region one slot to the right. ::impl{algo="quicksort_lomuto"} ## Hoare partition Hoare's original scheme uses two indices that march toward each other from the ends, swapping out-of-place pairs as they meet. It does fewer swaps on average than Lomuto and handles arrays with many duplicate keys more gracefully, at the cost of a subtler invariant (the returned index splits the array but is _not_ necessarily the pivot's final position). The two pointers $i$ and $j$ start outside the array and walk inward: $i$ stops at the first element $\ge x$ that does not belong on the left, $j$ at the first $\le x$ that does not belong on the right, and the pair is swapped. When the pointers cross, $j$ marks the boundary. $$ % caption: Hoare partition with pivot $x=A[p]$: $i$ scans right past small elements, $j$ % scans left past large ones, and the out-of-order pair $A[i],A[j]$ is swapped % before both resume marching inward. \begin{tikzpicture}[font=\small, >={Stealth[round]}, cell/.style={draw, minimum width=8mm, minimum height=8mm, font=\small}] \definecolor{acc}{HTML}{2348F2} % plain cells (skip the three highlighted positions 0,2,5) \foreach \v/\x in {2/1,1/3,9/4,7/6} \node[cell] at (\x,0) {$\v$}; % pivot = A[p] = 5 \node[cell, fill=acc!18, draw=acc, very thick] at (0,0) {$5$}; \node[font=\footnotesize, acc] at (0,0.95) {\texttt{pivot} $x$}; % i lands on 8 (>= x), j lands on 3 (<= x): the out-of-order pair \node[cell, fill=acc!12] at (2,0) {$8$}; \node[cell, fill=acc!12] at (5,0) {$3$}; \node[font=\scriptsize\itshape, acc] at (2,-0.95) {$i$}; \draw[->, acc] (2,-0.7) -- (2,-0.45); \node[font=\scriptsize\itshape, acc] at (5,-0.95) {$j$}; \draw[->, acc] (5,-0.7) -- (5,-0.45); % swap arrow between the two flagged cells, routed below the digits \draw[<->, red!75!black, thick] (2,-1.3) to[bend right=22] (5,-1.3); \node[font=\scriptsize, red!75!black] at (3.5,-1.95) {swap A[i] $\leftrightarrow$ A[j]}; \node[font=\scriptsize, anchor=west] at (7.4,0.3) {$i$ seeks $\ge x$}; \node[font=\scriptsize, anchor=west] at (7.4,-0.3) {$j$ seeks $\le x$}; \end{tikzpicture} $$ ```algorithm caption: $\textsc{Hoare-Partition}(A, p, r)$ — pivot $= A[p]$ number: 3 $x \gets A[p]$ // the pivot $i \gets p - 1$ $j \gets r + 1$ repeat repeat $j \gets j - 1$ until $A[j] \le x$ // scan down from right repeat $i \gets i + 1$ until $A[i] \ge x$ // scan up from left if $i < j$ then exchange $A[i]$ with $A[j]$ else return $j$ // split point: $A[p..j] \le A[j+1..r]$ ``` With Hoare partition the recursive calls become $\textsc{Quicksort}(A, p, j)$ and $\textsc{Quicksort}(A, j+1, r)$, since $j$ is a _boundary_ rather than the pivot's final index. Either scheme yields a correct, in-place quicksort; the difference lies purely in the constants and in robustness to duplicates. ::impl{algo="quicksort_hoare"} ## Duplicate keys The schemes differ most sharply on arrays with many equal elements — a common case in practice (sorting by year, by category, by grade). Take the extreme: an array of $n$ identical keys, which is of course already sorted. With **Lomuto**, every test $A[j] \le x$ succeeds, so $i$ marches in lockstep with $j$ and each swap is a self-swap. The loop ends with $i = r - 1$; the pivot "moves" to index $r$, and the split is $n-1$ elements versus $0$. Every level of recursion peels off one element: $\Theta(n^2)$ on a fully sorted, fully equal input, even though no element ever needs to move. With **Hoare**, both inner scans stop at elements _equal_ to the pivot: $j$ stops at the first $A[j] \le x$ and $i$ at the first $A[i] \ge x$, which on an all-equal array is one step each. The two indices walk toward each other one position per round, exchanging equal elements pointlessly but _crossing near the middle_. The split is balanced, and the sort finishes in $\Theta(n\log n)$. Those seemingly wasteful swaps of equal keys are what keep the split balanced. $$ % caption: An all-equal array. Lomuto classifies every element as $\le x$ and splits % $(n-1, 0)$ — quadratic. Hoare's converging scans swap equal pairs and cross in % the middle, splitting evenly. \begin{tikzpicture}[font=\small, >={Stealth[round]}, cell/.style={draw, minimum width=7mm, minimum height=7mm, font=\small}] \definecolor{acc}{HTML}{2348F2} % Lomuto row \node[font=\footnotesize, anchor=east] at (-0.7,0) {\texttt{Lomuto}}; \foreach \x in {0,1,2,3,4} \node[cell, fill=acc!12] at (\x,0) {$7$}; \node[cell, fill=acc!25, draw=acc, very thick] at (5,0) {$7$}; \draw[red!75!black, thick] (4.62,-0.55) -- (4.62,0.55); \node[font=\scriptsize, red!75!black, anchor=west] at (6.0,0.22) {split n-1 vs 0}; \node[font=\scriptsize, red!75!black, anchor=west] at (6.0,-0.28) {quadratic}; % Hoare row \node[font=\scriptsize, anchor=east] at (-0.7,-1.7) {Hoare}; \foreach \x in {0,1,2} \node[cell, fill=acc!12] at (\x,-1.7) {$7$}; \foreach \x in {3,4,5} \node[cell, fill=acc!6] at (\x,-1.7) {$7$}; \draw[acc, thick] (2.62,-2.25) -- (2.62,-1.15); \node[font=\scriptsize, acc, anchor=west] at (6.0,-1.48) {split n/2 vs n/2}; \node[font=\scriptsize, acc, anchor=west] at (6.0,-1.98) {balanced}; \end{tikzpicture} $$ The general fix is a **three-way partition** into $x$: group every key equal to the pivot into a middle block and recurse only on the strict sides. Duplicate-heavy inputs then get _faster_, not slower — an array of $k$ distinct keys sorts in $O(nk)$ partitioning work, and all-equal input becomes $O(n)$. The "Sort Colors" practice problem below applies this partition at $k = 3$. ## Worst case versus best case Partition is always $\Theta(n)$, so quicksort's total cost is governed entirely by how _balanced_ the splits are. **Worst case.** Suppose every partition is maximally lopsided, with one side empty and the other holding $n-1$ elements. This happens, for Lomuto with a last-element pivot, on an array that is already sorted (or reverse sorted). The [recurrence](/algorithms/foundations/recurrences) is $$ T(n) = T(n - 1) + T(0) + \Theta(n) = T(n-1) + \Theta(n) = \Theta(n^2). $$ The recursion tree degenerates into a path of depth $n$, with $\Theta(n)$ work at the top shrinking by one at each level: $n + (n-1) + \cdots + 1 = \Theta(n^2)$. Quicksort's worst case is no better than insertion sort. The reason a _sorted_ array is the worst case for Lomuto is simple: the last-element pivot $A[r]$ is then the **largest** value, so the whole scan stays $\le x$ and the partition peels off just the pivot, leaving an empty right side and an $(n-1)$-element left side to do it all again. $$ % caption: On a sorted array Lomuto's pivot $A[r]$ is the maximum, so every element is % $\le x$: partition strips off one element and recurses on the other $n-1$, the % maximally lopsided split. \begin{tikzpicture}[font=\small, >={Stealth[round]}, cell/.style={draw, minimum width=7mm, minimum height=7mm, font=\small}] \definecolor{acc}{HTML}{2348F2} \foreach \v/\x in {1/0,2/1,3/2,4/3,5/4} \node[cell, fill=acc!12] at (\x,0) {$\v$}; \node[cell, fill=acc!18, draw=acc, very thick] at (5,0) {$6$}; \node[font=\footnotesize, acc] at (5,0.92) {\texttt{pivot} = max}; \draw[acc] (-0.4,-0.6) -- (4.4,-0.6) node[midway, below, font=\scriptsize] {all $\le x$ (n-1 elements)}; \node[font=\scriptsize] at (5,-0.85) {alone}; \node[font=\footnotesize, red!75!black, anchor=west] at (6.0,0) {\texttt{right side empty}}; \end{tikzpicture} $$ **Best case.** If every partition splits evenly, the recurrence is the mergesort recurrence, $$ T(n) = 2\,T(n/2) + \Theta(n) = \Theta(n\log n). $$ **Near-balance suffices.** Balance need not be perfect. Even a fixed $9$-to-$1$ split gives $$ T(n) = T(9n/10) + T(n/10) + \Theta(n) = \Theta(n\log n), $$ because the recursion tree still has only $\Theta(\log n)$ levels (the longest root-to-leaf path shrinks by a factor of $10/9$ each step) and each level does $O(n)$ work. _Any_ split by a constant fraction yields $\Theta(n\log n)$. Only splits that are lopsided by a constant _number_ of elements, like the worst case, push us to quadratic. $$ % caption: Balanced splits keep the tree $\Theta(\log n)$ deep for a total of % $\Theta(n\log n)$; a constant-size lopsided split stretches it into a % depth-$n$ path costing $\Theta(n^2)$. \begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}] \definecolor{acc}{HTML}{2348F2} \node[font=\small] at (-2.6,2.3) {balanced}; \node[draw, fill=acc!10, minimum size=5mm] (a) at (-2.6,1.6) {$n$}; \node[draw, minimum size=4mm] (b) at (-3.6,0.7) {$\tfrac n2$}; \node[draw, minimum size=4mm] (c) at (-1.6,0.7) {$\tfrac n2$}; \node[draw, minimum size=3.6mm] (d) at (-4.1,-0.2) {$\tfrac n4$}; \node[draw, minimum size=3.6mm] (e) at (-3.1,-0.2) {$\tfrac n4$}; \node[draw, minimum size=3.6mm] (f) at (-2.1,-0.2) {$\tfrac n4$}; \node[draw, minimum size=3.6mm] (g) at (-1.1,-0.2) {$\tfrac n4$}; \draw[->](a)--(b);\draw[->](a)--(c);\draw[->](b)--(d);\draw[->](b)--(e);\draw[->](c)--(f);\draw[->](c)--(g); \node[font=\small] at (2.7,2.3) {worst case}; \node[draw, fill=acc!10, minimum size=5mm] (p) at (2,1.6) {$n$}; \node[draw, minimum size=4.4mm] (q) at (2.8,0.8) {$n$-1}; \node[draw, minimum size=4mm] (s) at (3.6,0) {$n$-2}; \node (t) at (4.3,-0.7) {...}; \draw[->](p)--(q);\draw[->](q)--(s);\draw[->](s)--(t); \end{tikzpicture} $$ Here is the $9$-to-$1$ tree in more detail. Every level still sums to at most $cn$, because the children of any node partition (at most) that node's elements. What changes is the _depth_: the left spine dies out after $\log_{10} n$ levels, the right spine survives for $\log_{10/9} n \approx 6.6 \log_2 n$ levels, and everything in between falls somewhere in the middle. A constant multiple of $\log n$ levels at $\le cn$ apiece is still $O(n \log n)$ — lopsidedness by a constant _fraction_ only bloats the constant. $$ % caption: The $9$-to-$1$ recursion tree: each level sums to at most $cn$, and even the % long right spine dies after $\log_{10/9} n = \Theta(\log n)$ levels, so the % total stays $O(n\log n)$. \begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \node[draw, fill=acc!10, minimum width=9mm] (a) at (1.2,3) {$n$}; \node[draw, minimum width=7mm] (b) at (-0.9,1.9) {$\tfrac{n}{10}$}; \node[draw, minimum width=8mm] (c) at (3.3,1.9) {$\tfrac{9n}{10}$}; \node[draw, minimum width=6mm] (d) at (-1.9,0.8) {$\tfrac{n}{100}$}; \node[draw, minimum width=6mm] (e) at (-0.1,0.8) {$\tfrac{9n}{100}$}; \node[draw, minimum width=6mm] (f) at (2.1,0.8) {$\tfrac{9n}{100}$}; \node[draw, minimum width=7mm] (g) at (4.4,0.8) {$\tfrac{81n}{100}$}; \node (h) at (-1.9,-0.1) {$\vdots$}; \node (i2) at (0.9,-0.1) {$\vdots$}; \node (j2) at (5.1,-0.1) {$\vdots$}; \draw[->] (a)--(b); \draw[->] (a)--(c); \draw[->] (b)--(d); \draw[->] (b)--(e); \draw[->] (c)--(f); \draw[->] (c)--(g); \draw[densely dashed, acc] (6.2,3) -- (7.6,3); \draw[densely dashed, acc] (6.2,1.9) -- (7.6,1.9); \draw[densely dashed, acc] (6.2,0.8) -- (7.6,0.8); \node[anchor=west, acc] at (6.2,3.3) {row sum = $cn$}; \node[anchor=west, acc] at (6.2,2.2) {row sum = $cn$}; \node[anchor=west, acc] at (6.2,1.1) {row sum = $cn$}; \end{tikzpicture} $$ ### The shrinking-recurrence lemma This "constant fraction is enough" intuition can be stated as a lemma that we will reuse for [linear-time selection](/algorithms/divide-and-conquer/selection). It says that as long as the recursive subproblems together are a _constant fraction smaller_ than the original, linear work at each level collapses to linear work overall. > **Lemma.** Let $\lambda, \mu, b > 0$ be constants with $\lambda + \mu < 1$. If > $T(n) \le T(\lambda n) + T(\mu n) + bn$ for all $n > n_0$ and $T(n) \le c$ for > $n \le n_0$, then $T(n) = O(n)$. The proof is a tidy induction that pins the hidden constant exactly. > **Proof.** Claim: $T(n) \le a n$ for all $n \ge 1$, where > $$ > a = \max\set{\,c,\ \frac{b}{1 - \lambda - \mu}\,}. > $$ > The constant $b/(1-\lambda-\mu)$ is positive _precisely because_ $\lambda + \mu < 1$; > that is where the shrinkage is spent. > - **Base case** ($n \le n_0$). $T(n) \le c \le a \le a n$. > - **Inductive step** ($n > n_0$). Assuming the bound for all smaller arguments, > $$ > \begin{aligned} > T(n) &\le T(\lambda n) + T(\mu n) + bn > \le a\lambda n + a\mu n + bn \\ > &= \parens{a(\lambda + \mu) + b}\,n > \le \parens{a(\lambda + \mu) + a(1 - \lambda - \mu)}\,n = a n, > \end{aligned} > $$ > where the last inequality uses $b \le a(1 - \lambda - \mu)$, which is how > $a$ was chosen. So $T(n) = O(n)$. $\qed$ For balanced quicksort the per-level work _grows_ a logarithmic number of times rather than collapsing, since the splits sum to the _whole_ array ($\lambda + \mu = 1$, the boundary case the lemma deliberately excludes), which is why quicksort is $\Theta(n\log n)$ and not $\Theta(n)$. The lemma's strict inequality $\lambda + \mu < 1$ is what separates "recurse on both halves" (sorting) from "throw away a constant fraction and recurse on one piece" (selection). ::impl{algo="shrinking_recurrence"} ## Why randomization helps The danger is a pivot rule that an adversary, or merely unlucky real-world data, can drive into the worst case. The fix is to **randomize**: choose the pivot uniformly at random from $A[p..r]$ (equivalently, swap a random element to the end before running Lomuto partition). ```algorithm caption: $\textsc{Randomized-Partition}(A, p, r)$ number: 4 $k \gets$ a uniformly random integer in $[p, r]$ exchange $A[k]$ with $A[r]$ // randomize pivot, reuse Lomuto return call $\textsc{Partition}(A, p, r)$ ``` Now no particular input is bad: the _coin flips_, not the input order, decide the split. The worst case still exists in principle (every random choice could be unlucky), but its probability is vanishingly small, and we can prove the **expected** running time is $\Theta(n\log n)$ on _every_ input.[^clrs-random] ::impl{algo="randomized_quicksort"} ### The expected-comparisons argument > **Theorem (Expected comparisons).** Randomized quicksort makes > $O(n\log n)$ comparisons in expectation on _every_ input. Let the sorted order of the elements be $z_1 < z_2 < \cdots < z_n$, and let $Z_{ij} = \set{z_i, \dots, z_j}$. Two elements are compared _at most once_ over the whole run, since comparisons only ever happen against a pivot, and a pivot is removed from future partitions. Define the indicator $X_{ij} = \mathbf{1}[z_i \text{ is compared with } z_j]$. The total comparison count is $X = \sum_{i={Stealth[round]}, cell/.style={draw, minimum width=7mm, minimum height=7mm, font=\small}] \definecolor{acc}{HTML}{2348F2} \node[cell, fill=acc!22] (zi) at (0,0) {$z_i$}; \node[cell] at (1,0) {}; \node[cell] (zm) at (2,0) {$z_m$}; \node[cell] at (3,0) {}; \node[cell, fill=acc!22] (zj) at (4,0) {$z_j$}; \draw[acc] (-0.45,-0.55) -- (4.45,-0.55) node[midway, below, font=\scriptsize] {range $Z_{ij}$}; \node[font=\footnotesize, acc] at (0,0.7) {\texttt{endpoint}}; \node[font=\footnotesize, acc] at (4,0.7) {\texttt{endpoint}}; \node[font=\footnotesize] at (2,1.05) {a middle \texttt{pivot} here separates them}; \draw[->] (2,0.8) -- (2,0.42); \end{tikzpicture} $$ Since the first pivot drawn from the $j - i + 1$ elements of $Z_{ij}$ is equally likely to be any of them, $$ \Pr[z_i \text{ compared with } z_j] = \frac{2}{\,j - i + 1\,}. $$ Substituting and reindexing with $k = j - i$, $$ \mathbb{E}[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} < \sum_{i=1}^{n-1} \sum_{k=1}^{n} \frac{2}{k} = 2\sum_{i=1}^{n-1} H_n = O(n\log n), $$ using the harmonic-number bound $H_n = \sum_{k=1}^n 1/k = \Theta(\log n)$. So randomized quicksort makes $\Theta(n\log n)$ comparisons in expectation, _regardless of the input arrangement_. Two sanity checks on the formula $2/(j - i + 1)$. Adjacent elements in sorted order ($j = i + 1$) are compared with probability $1$ — and indeed they must be: no third element can separate them, and a comparison sort that never compares them cannot know their order. Meanwhile the minimum and maximum ($i = 1$, $j = n$) are compared with probability $2/n$: almost any first pivot splits them apart immediately. ## Engineering the recursion A textbook quicksort recurses to $n = 1$ and uses whatever pivot rule it was given. Production quicksorts make three standard adjustments. **Pivot selection.** _Median-of-three_ pivots on the median of the first, middle, and last elements. It makes sorted and reverse-sorted inputs split perfectly instead of catastrophically, and it halves the chance of a bad split on random data. It is a heuristic, not a guarantee — fixed rules always leave some adversarial ordering quadratic, which is why libraries either randomize or monitor the recursion depth. **Cutoff to insertion sort.** As with [mergesort](/algorithms/divide-and-conquer/mergesort), recursing to singletons drowns small subarrays in call overhead. Below a threshold of $\approx 10$ elements, stop; either run insertion sort on each little piece, or (a classic trick) leave the pieces unsorted and finish with _one_ insertion-sort pass over the whole array, which is linear because every element is already within a constant distance of its final position. **Bounded stack.** Worst-case inputs threaten not just $\Theta(n^2)$ time but $\Theta(n)$ recursion depth — a stack overflow, not merely a slowdown. The fix is to recurse only into the _smaller_ side and loop on the larger one (tail-call elimination by hand). The recursive subproblem is then at most half its parent, so the stack never exceeds $\log_2 n$ frames, even when the running time degenerates. ## Quicksort versus mergesort | | Quicksort | Mergesort | | --- | --- | --- | | Worst case | $\Theta(n^2)$ | $\Theta(n\log n)$ | | Expected / average | $\Theta(n\log n)$ | $\Theta(n\log n)$ | | Extra space | $\Theta(\log n)$ (stack) | $\Theta(n)$ | | In place | yes | no | | Stable | no | yes | | Constants | small (cache-friendly) | larger | In practice **quicksort is usually the fastest comparison sort** on arrays in memory: it works in place, has tight inner loops, and accesses memory sequentially, a cache-friendly pattern.[^skiena-qs] Its weaknesses are the $\Theta(n^2)$ worst case (tamed by randomization or median-of-three pivoting) and instability. Mergesort wins when you need a worst-case guarantee, stability, or are sorting linked lists or data too large for memory. A common engineering compromise, _introsort_, runs quicksort but switches to [heapsort](/algorithms/sorting/heaps-and-heapsort) once the recursion depth exceeds $\Theta(\log n)$, capturing quicksort's speed with a worst-case $\Theta(n\log n)$ ceiling. ## What standard libraries ship Introsort was the 1997 answer; the sorts shipping in today's standard libraries have moved past it in two directions. **Pattern-defeating quicksort (pdqsort).** The heuristics of the previous section each leave _some_ input slow. **pdqsort** (Peters, 2016), now the unstable `sort_unstable` in Rust and the basis of libc++'s `std::sort`, hardens them into guarantees. It keeps introsort's heapsort fallback for the worst case, but adds two adaptive tricks: it detects already-sorted or reverse-sorted runs and short-circuits them toward linear time, and — the "pattern-defeating" part — when it notices a partition was badly unbalanced (a sign an adversary or bad pattern is at work) it injects randomness into pivot choice for that subtree, so no fixed input pattern stays quadratic. It captures median-of-three's speed on ordinary data, adaptivity on structured data, and a hard $\Theta(n\log n)$ ceiling, all at once. **Dual-pivot partitioning.** Java's `Arrays.sort` for primitives uses a **dual-pivot quicksort** (Yaroslavskiy, 2009): pick two pivots $p \le q$ and partition into three regions — $< p$, between $p$ and $q$, and $> q$ — in a single sweep. It does more comparisons per element than the classic scheme but noticeably _fewer_ cache misses and data movements, and on modern memory hierarchies that trade wins. It is a reminder that the comparison count, the quantity this lesson's analysis minimizes, is no longer the whole cost on real hardware. **Fighting branch misprediction: BlockQuicksort.** On a modern CPU the hidden cost of partitioning is the _unpredictable branch_ `if A[j] <= x`: half the time it mispredicts, flushing the pipeline. **BlockQuicksort** (Edelkamp and Weiß, 2016) removes the branch by computing, for a block of elements at a time, an array of indices that need swapping and then swapping them with straight-line, branchless code. The comparison count is unchanged, but eliminating the mispredictions makes it substantially faster in wall-clock time — another case where the theoretical model and the machine disagree, and the engineering follows the machine. ## Takeaways - $\textsc{Quicksort}$ front-loads the work into $\textsc{Partition}$; once the array is partitioned around a pivot $x$ into $< x \mid x \mid > x$, the pivot is in its final slot and the recursive sorts need no combine step. - $\textsc{Lomuto}$ (single sweep, pivot at the end) and $\textsc{Hoare}$ (two converging indices) are both correct via partition loop invariants; Hoare does fewer swaps and handles duplicates better. - Cost is set by split balance: lopsided-by-a-constant gives $\Theta(n^2)$, but _any_ constant-fraction split gives $\Theta(n\log n)$. The shrinking-recurrence lemma ($\lambda + \mu < 1 \Rightarrow T(n) = O(n)$) makes "constant fraction is enough" rigorous and powers linear-time selection next door. - **Randomizing the pivot** makes the expected cost $\Theta(n\log n)$ on every input; the proof counts each pair's $2/(j-i+1)$ chance of being compared. - **Duplicates** expose the schemes' difference: all-equal input drives Lomuto quadratic while Hoare stays balanced; a three-way $x$ partition makes duplicate-heavy inputs faster, not slower. - Production quicksorts add median-of-three pivoting, an insertion-sort cutoff for small subarrays, and smaller-side-first recursion to cap the stack at $O(\log n)$. - Quicksort is typically the fastest in-memory sort; mergesort wins on worst-case guarantees, stability, and external data. [^erickson-qs]: **Erickson**, _Algorithms_, Ch. 1 — Recursion: quicksort as divide-and-conquer that front-loads the work into partitioning, leaving an empty combine step. [^clrs-lomuto]: **CLRS**, Ch. 7 — Quicksort: the Lomuto single-sweep partition scheme and its four-region loop invariant. [^clrs-random]: **CLRS**, Ch. 7 — Quicksort: randomized quicksort and the proof that its expected comparison count is $\Theta(n\log n)$ on every input. [^skiena-qs]: **Skiena**, _The Algorithm Design Manual_, §4 — Sorting and Searching: quicksort as the fastest in-memory comparison sort in practice, and the role of pivot selection.