Quicksort and selection

Mergesort guarantees $Θ (n \log n)$ and pays for it with a second array the size of the first, and quicksort is the trade in the other direction.

Partition

The idea is to divide the work before the recursion rather than after it. Choose one element as the pivot and rearrange the array so that everything not greater than the pivot comes first, then the pivot, then everything greater. The pivot is now in its final sorted position, and the two sides can be sorted independently with no combination step at all: no merge, no extra array.

The Lomuto scheme does this in one pass. Take the last element as pivot. Keep an index $i$ marking the end of the small region, initially before the start. Sweep $j$ across the rest; whenever $a [j]$ is not greater than the pivot, advance $i$ and swap $a [i]$ with $a [j]$ . At the end, swap the pivot into position $i + 1$ . The invariant is that $a [0.. i]$ holds elements not greater than the pivot and $a [i + 1.. j - 1]$ holds elements greater.

Partitioning $n$ elements costs exactly $n - 1$ comparisons and at most $n$ swaps, and uses no memory beyond a few indices.

Example. Partition 7, 2, 9, 4, 1, 6, 8, 3 with the last element as pivot, using Lomuto. Show the array after each swap.

The pivot is 3 and $i$ starts at $- 1$ . At $j = 0$ , $7 > 3$ , nothing. At $j = 1$ , $2 \leq 3$ , so $i$ becomes 0 and $a [0]$ swaps with $a [1]$ : 2, 7, 9, 4, 1, 6, 8, 3. At $j = 2$ and $j = 3$ , 9 and 4 both exceed 3. At $j = 4$ , $1 \leq 3$ , so $i$ becomes 1 and $a [1]$ swaps with $a [4]$ : 2, 1, 9, 4, 7, 6, 8, 3. At $j = 5$ and $j = 6$ , 6 and 8 exceed 3. Finally the pivot swaps into position $i + 1 = 2$ : 2, 1, 3, 4, 7, 6, 8, 9. Seven comparisons, three swaps, and 3 is in its final place.

Now you. Partition 5, 8, 1, 3, 9, 2, 7, 4 the same way.

Answer

Pivot 4, $i = - 1$ . At $j = 2$ , $1 \leq 4$ : $i = 0$ , swap giving 1, 8, 5, 3, 9, 2, 7, 4. At $j = 3$ , $3 \leq 4$ : $i = 1$ , swap giving 1, 3, 5, 8, 9, 2, 7, 4. At $j = 5$ , $2 \leq 4$ : $i = 2$ , swap giving 1, 3, 2, 8, 9, 5, 7, 4. Final swap puts the pivot at index 3: 1, 3, 2, 4, 9, 5, 7, 8. Notice that 5 and 8 have changed their relative order although neither was compared with the other, which is why quicksort is not stable.

The other standard scheme is Hoare's, from his original 1961 papers: two indices walk inward from the ends, each stopping at an element belonging on the other side, and the two are swapped. It does about three times fewer swaps than Lomuto and behaves far better on arrays containing many equal keys, which is why library implementations use it or a three-way variant of it. Lomuto is presented here because its invariant is easier to state, not because it is better.

Quicksort, and its two extremes

Quicksort is partition plus recursion: partition, then sort the part left of the pivot and the part right of it. The base case is a range of one element or none.

If the pivot always lands in the middle, the recurrence is $T (n) = 2 T (n / 2) + Θ (n)$ , the same as mergesort's, giving $Θ (n \log n)$ .

If the pivot always lands at one end, the two subproblems are of size $0$ and $n - 1$ , and

T (n) = T (n - 1) + Θ (n) ⟹ T (n) = Θ (n^{2})

with about $n^{2} / 2$ comparisons: 500 billion on a million elements, some eight minutes, against a fiftieth of a second.

The worst case is not a remote possibility, and this is the part that matters in practice. With the last element as pivot, an already sorted array produces exactly this behaviour: the pivot is the maximum every time. So does a reverse-sorted array, and so does an array of identical values under a naive two-way partition. Sorted input is the most common input shape there is. A textbook quicksort is therefore quadratic on exactly the data people feed it, and it also recurses $n$ deep, which overflows the call stack long before it finishes.

The average case

Between the extremes, the behaviour is far closer to the good end than intuition suggests, and the derivation is worth doing.

Assume all $n!$ orderings of distinct elements are equally likely, so the pivot is equally likely to be the $k$ -th smallest for each $k$ from 1 to $n$ . Partitioning costs $n - 1$ comparisons and leaves subproblems of size $k - 1$ and $n - k$ . So the expected comparison count satisfies

C (n) = (n - 1) + \frac{1}{n} \sum_{k = 1}^{n} [C (k - 1) + C (n - k)]

The sum contains every $C (0)$ through $C (n - 1)$ exactly twice, so it simplifies to $C (n) = (n - 1) + \frac{2}{n} \sum_{j = 0}^{n - 1} C (j)$ . Solving it, by multiplying through by $n$ , subtracting the same equation for $n - 1$ and telescoping, gives the exact closed form

C (n) = 2 (n + 1) H_{n} - 4 n

where $H_{n} = 1 + \frac{12}{+} \frac{13}{+} \dots + \frac{1}{n}$ is the harmonic number. Since $H_{n} \approx \ln n + 0.5772$ , this is asymptotically $2 n \ln n \approx 1.386 n \log_{2} n$ .

Put numbers on it. For a million elements the formula gives 24.8 million comparisons. Mergesort's worst case is 18.9 million. So quicksort makes about 31 per cent more comparisons on average, and by the time $n$ is large enough for the lower-order terms to fade, about 39 per cent more.

That is the whole cost, and quicksort is still typically faster than mergesort in practice. The reasons are all outside the comparison count: it moves each element about a third as often, it writes into the array it is already reading rather than into a second one, its inner loop is a sequential scan that the hardware prefetcher predicts perfectly, and it allocates nothing. This is a clean example of the warning from the second lesson: two algorithms with the same asymptotic class can differ by a factor of two or three on constants alone, and the count does not see it.

Example. Using $C (n) = 2 (n + 1) H_{n} - 4 n$ with $H_{1000} \approx 7.485$ , how many comparisons does quicksort average on 1000 elements, and how does that compare with $n \log_{2} n$ ?

$C (1000) = 2 \times 1001 \times 7.485 - 4000 = 14 {,} 985 - 4000 = 10 {,} 985$ comparisons. Meanwhile $n \log_{2} n = 1000 \times 9.966 = 9966$ . Quicksort averages about 10 per cent more at this size, and the gap widens slowly towards 39 per cent as $n$ grows, because the $- 4 n$ term fades relative to $2 n \ln n$ .

Now you. With $H_{100} \approx 5.187$ , how many comparisons does quicksort average on 100 elements?

Answer

$C (100) = 2 \times 101 \times 5.187 - 400 = 1047.8 - 400 = 647.8$ comparisons, against $n \log_{2} n = 664.4$ . At this size quicksort actually averages slightly fewer comparisons than $n \log_{2} n$ , because the $- 4 n$ correction still dominates. The asymptotic constant 1.386 is a statement about large $n$ and misleads at small $n$ , which is exactly what the second lesson warned about.

Randomising the pivot

The average-case result assumed a random input, which is an assumption about the world and therefore not a guarantee. The fix is to stop assuming and start enforcing: choose the pivot uniformly at random from the range being partitioned, and swap it to the end before partitioning.

That single change moves the randomness from the input to the algorithm. The expected cost is now $2 (n + 1) H_{n} - 4 n$ for every input, including sorted ones, because the analysis no longer depends on the arrangement of the data at all. There remains a worst case, but no adversary who does not see the random numbers can arrange for it.

How unlikely is bad behaviour? A random pivot falls between the 25th and 75th percentile with probability $1 / 2$ , and such a split leaves the larger side with at most $3 / 4$ of the elements. So on any root-to-leaf path, about half the splits are "good", and $\log_{4 / 3} 10^{6} = 48$ good splits suffice to reduce a million elements to one. The recursion depth is therefore $O (\log n)$ with overwhelming probability. Getting the quadratic case requires near-extreme pivots almost every time for a million consecutive independent choices, and the probability is far below any risk that is worth engineering against.

The cheap alternative is median of three: take the median of the first, middle and last elements as pivot. It makes sorted input into a best case rather than a worst case and costs almost nothing, and it is what most implementations did for decades. It is not a guarantee. In 1999 Doug McIlroy published A Killer Adversary for Quicksort, a comparison function that watches which comparisons a median-of-three quicksort makes and answers them so as to force the quadratic case, without ever contradicting itself. Any deterministic pivot rule can be defeated this way, which matters when the data comes from an untrusted source: a service that sorts user-supplied input with a deterministic quicksort can be brought down by a carefully chosen request. That is why randomisation, or a hard fallback, is the right answer and median-of-three alone is not.

The hard fallback is introsort, published by David Musser in 1997 and now the basis of std::sort. It runs quicksort but counts the recursion depth, and if it exceeds about $2 \log_{2} n$ it abandons quicksort for heapsort on that subrange. The result has quicksort's speed in the ordinary case and heapsort's $Θ (n \log n)$ guarantee in every case. Below a threshold of around 16 elements it switches again, to insertion sort, for the reason established two lessons ago. Practically every industrial sort is a hybrid of three algorithms, and it is worth knowing that none of them ships in the pure form taught here.

The same partition, used once

Partitioning is useful on its own, because it answers a question that does not require a full sort. Finding the $k$ -th smallest element of an unsorted array is the selection problem, and $k = n / 2$ is the median.

The obvious route is to sort and index, costing $Θ (n \log n)$ . But after one partition, the pivot sits at some index $p$ , and you know immediately which side the answer is on: if $p = k$ you are done; if $k < p$ the answer lies to the left; otherwise to the right. So recurse into one side only. That is quickselect, Hoare's, from the same 1961 work.

With balanced splits the recurrence is

T (n) = T (n / 2) + Θ (n) ⟹ T (n) = Θ (n)

because the level costs form a geometric series $n + n / 2 + n / 4 + \dots < 2 n$ rather than staying constant. The expected comparison count with random pivots is $2 n$ for finding the minimum and about $2 (1 + \ln 2) n \approx 3.39 n$ for the median. Linear, with a small constant, to find the median of an unsorted array without sorting it.

The worst case is still $Θ (n^{2})$ , and here there is a genuine repair rather than just a probabilistic one: the median-of-medians algorithm of Blum, Floyd, Pratt, Rivest and Tarjan (1973) picks a pivot guaranteed to be between the 30th and 70th percentiles, giving worst-case $Θ (n)$ . Its constant is large enough that it is rarely used directly, and its usual role is as the fallback inside a randomised implementation.

Example. Using the partition performed in the first example, which left 2, 1, 3, 4, 7, 6, 8, 9 with the pivot 3 at index 2, find the 3rd smallest element.

The 3rd smallest is at index 2 in 0-based terms, and the pivot is exactly there. So the answer is 3, found after a single partition and seven comparisons, with no sorting of either side. Had the target been index 5, the search would continue into the right part 7, 6, 8, 9 only, discarding the other three elements permanently.

Now you. Using the second partition, 1, 3, 2, 4, 9, 5, 7, 8 with pivot 4 at index 3, find the 5th smallest element.

Answer

The 5th smallest is at index 4. The pivot is at index 3, so the answer is in the right part, 9, 5, 7, 8, occupying indices 4 to 7, and specifically it is the smallest of that part. Partitioning that part, or simply scanning it, gives 5. Total work: seven comparisons for the first partition and three for the scan, ten, against the 17 comparisons mergesort would need to sort all eight.

Where this leaves sorting

There are now two $Θ (n \log n)$ sorts with opposite trades: mergesort, guaranteed and stable and hungry for memory; quicksort, in place and faster in practice and guaranteed only once randomised or bounded by a fallback.

Neither is meaningfully below $n \log_{2} n$ comparisons, and mergesort's worst case of $n \log_{2} n - n + 1$ is suspiciously close to the $n \log_{2} n$ that the shape suggests. That raises a question the course can now actually answer: is $n \log n$ the end of the road, or just the best anybody has managed? The next lesson proves it is the end of the road for every algorithm that sorts by comparing, and then shows two algorithms that finish in linear time by not comparing.