A Θ(n²) worst case that nobody minds, because randomization makes it Θ(n lg n) expected on every input and the constant factor beats everything else.
Quicksort is the sort that actually runs on your machine. Its worst case is quadratic — strictly worse than merge sort and heapsort — yet it is the standard choice for in-memory sorting, because its expected running time is Θ(n lg n) with a very small constant, it sorts in place, and its memory access pattern is sequential enough to keep caches happy. This chapter is also the first serious payoff from Chapter 5: the expected-time analysis is a single elegant application of indicator random variables.
PARTITION shown is the Lomuto scheme, which CLRS has always used because it is easier to prove correct; production code more often uses Hoare’s scheme, covered in Problem 7-1.Quicksort is divide-and-conquer, but with the work distributed very differently from merge sort.
| Step | Merge sort | Quicksort |
|---|---|---|
| Divide | Trivial: split at the midpoint, Θ(1) | All the work: partition around a pivot, Θ(n) |
| Conquer | Two recursive calls on n/2 | Two recursive calls on the two sides |
| Combine | All the work: merge, Θ(n) | Trivial: nothing to do, Θ(1) |
≤ it and everything right is > it, so once both sides are sorted the whole array is sorted — no merge step exists. That is why quicksort needs no scratch array.QUICKSORT(A, p, r)
1 if p < r
2 q = PARTITION(A, p, r) // partition and get the pivot's final index
3 QUICKSORT(A, p, q-1) // sort the low side
4 QUICKSORT(A, q+1, r) // sort the high sideCall it as QUICKSORT(A, 1, n). Note the pivot at index q is excluded from both recursive calls — it is already in its final position.
Everything interesting happens here. PARTITION takes the last element as the pivot and rearranges A[p:r] in place so that small elements come first, then the pivot, then large elements.
PARTITION(A, p, r)
1 x = A[r] // the pivot
2 i = p - 1 // highest index into the low side
3 for j = p to r - 1 // process each element except the pivot
4 if A[j] ≤ x // does this element belong on the low side?
5 i = i + 1 // open a new slot on the low side
6 exchange A[i] with A[j]
7 exchange A[i+1] with A[r] // drop the pivot just past the low side
8 return i + 1 // the pivot's final indexOne pass, one comparison per element, at most one swap per element: Θ(n) on a subarray of n elements.
Two pointers do the work. j scans forward through the unexamined region; i marks the end of the growing low side. Whenever j finds an element that belongs on the low side, i advances to claim the next slot and the two elements trade places.
The correctness argument is a four-region picture, and it is worth carrying because it makes the two-pointer dance obvious.
i, and j feeds them one element at a time from the grey region.k: (1) if p ≤ k ≤ i then A[k] ≤ x; (2) if i+1 ≤ k ≤ j-1 then A[k] > x; (3) if k = r then A[k] = x.i = p-1 and j = p, so regions (1) and (2) are both empty and the conditions hold vacuously. Condition (3) holds by line 1.A[j] > x, incrementing j extends region (2) by the element just examined. If A[j] ≤ x, incrementing i and swapping moves the leftmost element of region (2) out to position j and puts A[j] at the end of region (1). Both regions keep their property.j = r, so every element is in region (1), region (2), or is the pivot. Line 7 swaps the pivot with the first element of region (2), placing it exactly between the two, which is its final sorted position.Two consequences worth noting. The pivot ends up in its correct final position, which is why it is excluded from both recursive calls — that is the invariant that drives the whole recursion. And PARTITION is not stable: line 6 swaps across arbitrary distances.
Θ(n²)The worst case is a maximally unbalanced partition, where one side gets n-1 elements and the other gets none. That happens when the pivot is the largest or smallest element of the subarray, every time.
T(n) = T(n-1) + T(0) + Θ(n)
= T(n-1) + Θ(n)
= Θ(n²) // unrolls to an arithmetic seriesA[r] as the pivot, an already-sorted array triggers it: the last element is the largest, so every partition puts n-1 elements on the low side and nothing on the high side. A reverse-sorted array does the same. Sorted and nearly-sorted arrays are extremely common in practice, so deterministic quicksort with a last-element pivot is a genuinely bad idea — and worse, an attacker who knows your pivot rule can hand you a quadratic input on purpose. This is a real denial-of-service vector, and it has been exploited against real systems.Note the irony against insertion sort: the input that is best for insertion sort is worst for quicksort.
The best case splits evenly:
T(n) = 2T(n/2) + Θ(n) = Θ(n lg n) // master case 2The important question is what happens between the extremes. The answer is the most reassuring result in the chapter: any split by a constant fraction is as good as an even one, asymptotically.
Suppose every partition splits 9 to 1 — badly lopsided by any intuition:
T(n) = T(9n/10) + T(n/10) + Θ(n) = O(n lg n)Why: in the recursion tree, the shortest root-to-leaf path shrinks by a factor of 10 each level and so has depth log₁₀ n; the longest shrinks by a factor of 10/9 and has depth log₁₀⃗₉ n. Both are Θ(lg n), differing only in the base, which is a constant factor. Each level costs at most cn. So the total is O(n lg n).
O(n lg n). Even a 99-to-1 split does. The bound only breaks when the split fraction itself depends on n.O(n lg n) whenever the partition is balanced by any constant fraction, however lopsided. A 99-to-1 split gives log₁₀₀⃗₉₉ n depth, which is about 69× deeper than lg n — a big constant, but still a constant. Disaster requires splits that are lopsided in a way that scales with n, such as always peeling off exactly one element.In the average case partitions are a mix of good and bad. The chapter offers an intuition pump: suppose the splits alternate between the best possible and the worst possible. A bad split costs Θ(n) and produces subproblems of size 0 and n-1; the good split of that n-1 then costs Θ(n) again and yields two halves.
The pair of levels costs Θ(n) and achieves what a single good split would have. So the recursion is Θ(n lg n) with roughly twice the constant. The bad splits are absorbed into the constant factor. This is why quicksort is not fragile in practice — you need bad splits consistently, not occasionally, to hurt it.
The intuition above still assumes something about the input. Chapter 5 supplies the fix: put the randomness in the algorithm.
RANDOMIZED-PARTITION(A, p, r)
1 i = RANDOM(p, r)
2 exchange A[r] with A[i] // a random element becomes the pivot
3 return PARTITION(A, p, r)
RANDOMIZED-QUICKSORT(A, p, r)
1 if p < r
2 q = RANDOMIZED-PARTITION(A, p, r)
3 RANDOMIZED-QUICKSORT(A, p, q-1)
4 RANDOMIZED-QUICKSORT(A, q+1, r)Two extra lines. Swapping a random element into the last position lets PARTITION stay exactly as it was.
Θ(n lg n) for every input, and an adversary who can see your input cannot construct a slow case without also seeing your random numbers.This is the highlight of the chapter and one of the best arguments in the book. The goal: show that RANDOMIZED-QUICKSORT runs in expected O(n lg n) time.
Every call to PARTITION does O(1) work plus one comparison per element scanned. PARTITION is called at most n times overall, since each call places one pivot permanently. So if X is the total number of comparisons across all partition calls, the running time is O(n + X). It remains to bound E[X].
Rename the elements z₁, z₂, …, zₙ in sorted order, so zᵢ is the ith smallest. Let Zᵢⱼ = {zᵢ, zᵢ₊₁, …, zⱼ} be the set of elements between them inclusive. Define
Xᵢⱼ = I{ zᵢ is compared to zⱼ at some point }
X = ∑ from i=1 to n-1 ∑ from j=i+1 to n of XᵢⱼThe critical structural observation:
zᵢ and zⱼ can be compared only in the single call where one of them is the pivot — never again.When does zᵢ get compared to zⱼ? Consider the elements of Zᵢⱼ and ask which one is chosen as a pivot first. Before any of them is a pivot, they are all in the same subproblem, because no pivot so far has fallen between them.
Zᵢⱼ is zᵢ or zⱼ, then that pivot is compared against every other element of the set, including the other one. They are compared.zₖ strictly between them, then zᵢ goes to the low side and zⱼ to the high side. They land in different subproblems and are never compared.Each of the j - i + 1 elements of Zᵢⱼ is equally likely to be the first pivot chosen from the set. Two of them are favourable. So
Pr{zᵢ is compared to zⱼ} = 2 / (j - i + 1)E[X] = ∑ᵢ ∑ⱼ 2/(j-i+1)
= ∑ from i=1 to n-1 ∑ from k=1 to n-i of 2/(k+1) // let k = j-i
< ∑ from i=1 to n-1 ∑ from k=1 to n of 2/k
= ∑ from i=1 to n-1 of 2·Hₙ // harmonic number again
= O(n lg n)So the expected running time of randomized quicksort is O(n + X) = O(n lg n).
Xᵢⱼ are wildly dependent, and linearity of expectation does not care — exactly the freedom Chapter 5 promised.Notice also what the probability formula says qualitatively: 2/(j-i+1) means nearby elements are very likely to be compared and distant ones are not. Adjacent elements zᵢ and zᵢ₊₁ are compared with probability 1 — they must be, since nothing can separate them. The smallest and largest elements are compared with probability 2/n.
Textbook quicksort is not what ships. The standard production version adds four things:
| Refinement | What it fixes |
|---|---|
| Median-of-three pivot | Take the median of the first, middle, and last elements. Cheap, and it makes sorted and reverse-sorted input the best case rather than the worst. Many libraries use median-of-nine for large arrays. |
| Insertion sort below a threshold | Stop recursing when the subarray drops under roughly 16 elements and finish with one insertion-sort pass over the whole array. Kills the recursion overhead where it dominates. |
| Tail-call elimination | Recurse on the smaller side and loop on the larger. This caps stack depth at O(lg n) instead of O(n), which matters because the worst case would otherwise overflow the stack. |
| Three-way partitioning | Split into < x, = x, and > x. With many duplicate keys, Lomuto’s two-way partition degrades toward Θ(n²); three-way makes duplicates the best case. This is the Dutch national flag problem, Problem 7-1 territory. |
PARTITION above. Every element satisfies A[j] ≤ x, so i advances every iteration and the pivot lands at the far right — a maximally unbalanced split, every time, giving Θ(n²). Randomizing the pivot does not help, because every pivot is the same value. This bug shipped in real sort implementations and is why three-way partitioning is standard now.Hoare’s original partition scheme, which works two pointers inward from both ends, does about three times fewer swaps than Lomuto’s and handles duplicates far better. CLRS uses Lomuto’s in the main text purely because its invariant is easier to state; Hoare’s appears in Problem 7-1 and is what most libraries actually implement.
n lg n sorts side by side| Merge sort | Heapsort | Quicksort (randomized) | |
|---|---|---|---|
| Worst case | Θ(n lg n) | Θ(n lg n) | Θ(n²) |
| Expected | Θ(n lg n) | Θ(n lg n) | Θ(n lg n) |
| Extra space | Θ(n) | Θ(1) | Θ(lg n) stack |
| Stable | Yes | No | No |
| Cache behaviour | Good | Poor | Excellent |
| Constant factor | Medium | Large | Small |
| Typical use | External sorting, stable sorts, linked lists | Guaranteed bound in O(1) space | Default in-memory sort |
2 lg n, switch that subproblem to heapsort. You get quicksort’s speed with a hard O(n lg n) guarantee.PARTITION does the sorting; there is no combine step, which is why it needs no scratch array.PARTITION invariant: four regions — ≤ x up to i, > x from i+1 to j-1, unexamined from j, pivot at r. The pivot ends in its final position, so it is excluded from both recursive calls.Θ(n²) on maximally unbalanced splits, which for a last-element pivot means already-sorted input — an ordinary input, not an exotic one.Θ(n lg n), and so is any constant-fraction split. A 99-to-1 split is still O(n lg n); only splits that get lopsided with n hurt.Θ(n lg n): bad splits get absorbed into the constant.Θ(n lg n) on every input. No bad inputs, only unlucky runs.zᵢ and zⱼ are compared exactly when the first pivot drawn from Zᵢⱼ is one of them, with probability 2/(j-i+1); summing gives a harmonic series and O(n lg n).Θ(n²) even with a random pivot.Merge sort, heapsort, and quicksort all reach Θ(n lg n) and none does better. Chapter 8 explains why that is not a coincidence: any sort that works by comparing elements needs Ω(n lg n) comparisons in the worst case, proved with a decision-tree argument. It then shows how to beat the bound by refusing to play — counting sort, radix sort, and bucket sort run in linear time by exploiting structure in the keys rather than comparing them.