Quicksort

Mergesort does its hard work in the combine step: splitting is trivial, merging is where the sorting happens. $\text{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.¹

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+\mathrm{1..}r]$.
• Combine. Nothing to do: the subarrays are already in place and in order relative to each other.

Everything hinges on $\text{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

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 exactly why the combine step vanishes. The whole game of quicksort is to make this split, and to make 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.²

Correctness of partition

Partition is correct by a four-region loop invariant. At the start of each iteration of the for loop, for any array index:

• 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.

• 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: exactly the postcondition, and $i+1$ is the pivot's final position $q$.

Partition does $\Theta (n)$ comparisons on $n=r-p+1$ elements.

A snapshot of the sweep makes the four regions concrete. On $A=⟨2,8,7,1,3,5,6,4⟩$ 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:

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 resting place).

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.

With Hoare partition the recursive calls become $\text{Quicksort}(A,p,j)$ and $\text{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.

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 is

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 villain for Lomuto is concrete: 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.

Best case. If every partition splits evenly, the recurrence is the mergesort recurrence,

The happy surprise. Balance need not be perfect. Even a fixed $9$-to-$1$ split gives

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.

The shrinking-recurrence lemma

This constant-fraction is enough intuition packages into a clean lemma that we will reuse for linear-time 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.

The proof is a tidy induction that pins the hidden constant exactly. Claim: $T(n)\le an$ for all $n\ge 1$, where

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 an$.
• Inductive step ($n>n_0$). Assuming the bound for all smaller arguments,

where the last inequality uses $b\le a(1-\lambda -\mu )$, which is exactly how $a$ was chosen. So $T(n)=O(n)$. $■$

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).

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).

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.³

The expected-comparisons argument

Let the sorted order of the elements be $z_1<z_2<\cdots <z_n$, and let $Z_{ij}=\left\{z_i,\dots ,z_j\right\}$. 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}=1[z_i\text{ is compared with }{z}_j]$. The total comparison count is $X={\sum }_{i<j}{X}_{ij}$, so by linearity of expectation

The combinatorial fact that matters: $z_i$ and $z_j$ are compared iff the first pivot chosen from the range $Z_{ij}$ is either $z_i$ or $z_j$. If instead some middle element $z_m$ (with $i<m<j$) is picked first, it splits $z_i$ and $z_j$ into different subarrays and they never meet.

Since the first pivot drawn from the $j-i+1$ elements of $Z_{ij}$ is equally likely to be any of them,

Substituting and reindexing with $k=j-i$,

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.

Quicksort versus mergesort

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, which the cache loves.⁴ 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 once the recursion depth exceeds $\Theta (\log n)$, capturing quicksort's speed with a worst-case $\Theta (n\log n)$ ceiling.

Takeaways

• $\text{Quicksort}$ front-loads the work into $\text{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.
• $\text{Lomuto}$ (single sweep, pivot at the end) and $\text{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.
• Quicksort is typically the fastest in-memory sort; mergesort wins on worst-case guarantees, stability, and external data.