Quicksort's cost is the sum of the subarray sizes it partitions, so the split decides everything and the pivot rule decides the split. Every deterministic rule is a function of the array, which means an array can be built against it: the lab builds one by answering the rule's own comparisons adversarially, then runs the ordinary quicksort on what comes out and counts.
Core ideas
The hard idea is that a pivot rule is a claim about inputs, and a claim about inputs can be attacked by choosing one.
Each call partitions its range at a cost of one less than its length, then recurses on the two pieces. So the total comparison count is the sum, over every call, of that call's length minus one — nothing else. A balanced split halves the length each level, giving about log₂ n levels of about n work; a split that peels off one element at a time gives n levels, and (n−1) + (n−2) + … + 1 = n(n − 1)/2.
Take the first element, the middle element, the median of three named positions: each is a rule that reads the array and returns a position. Run the rule and answer each of its comparisons so as to keep the worst case reachable, and what falls out is a permutation on which that rule is bad every time. The lab does this rather than quoting an array from a paper, and then hands the array to the ordinary quicksort, which measures it: 304 comparisons for median of three at 32 keys, where n log₂ n is 160.
Median of three is a real improvement on sorted input — 151 comparisons at 32 keys where a first-element pivot pays 496. It is not a bound, because its own killer exists and the lab ships it. And the killer is rule-specific: the array built against median of three costs a first-element pivot only 143, because a bad input for one rule is not a bad input for another.
The material
Where quicksort's comparisons come from, what the split does to them, and how an input is constructed to make the split bad.
To quicksort a[lo..hi]: if the range holds fewer than two elements, stop. Otherwise partition it around a pivot chosen by a pivot rule, then quicksort the part left of the pivot and the part right of it. The pivot itself is never looked at again.
There is no merge step and no extra array. All the work is in the partitions, and by “Partitioning” each partition of a range of length m costs m − 1 comparisons. So the comparison count of a whole run is determined by the multiset of range lengths the recursion visits, and that is determined by the splits.
Those two lines are the same recurrence with two values of k, and the gap between their solutions is the whole subject of the lesson. Discrete Mathematics' “Divide and Conquer” solves the first by the master theorem and “Recursion Trees and Amortised Analysis” gives the tree argument the second one is a degenerate case of. Neither tells you which k you get; the pivot rule and the input do.
The pivot is the smallest key, so k = 0: the left side is empty and the right side has n − 1 elements. Then the same thing happens again. At 32 keys the lab measures 496 comparisons and a recursion depth of 31, against n(n − 1)/2 = 496 — the recurrence's worst case, met exactly. Already-sorted input is the commonest input there is, which is what makes this rule not merely theoretically bad.
The lab's killer input is constructed, not recalled. It runs the chosen rule on n items whose values are not yet decided, and whenever the rule compares two undecided items it freezes one of them at the next smallest value available — choosing which one so that the pivot keeps turning out to be near the smallest thing left. Every answer it gives is consistent with the values it finally hands back, so what comes out is a real permutation of 1 … n and not a trick.
That is the same manoeuvre as the lower-bound arguments at the end of this course: answer the algorithm's questions so as to keep the bad case alive. Here it is aimed at one rule rather than at every algorithm, which is why it produces an input rather than a bound.
At 32 keys the array the lab builds is 1 18 4 26 6 20 8 30 10 22 12 28 14 24 16 2 3 5 7 … and the adversary answered 316 of the rule's comparisons while building it. The ordinary quicksort then spends 304 comparisons on it and recurses 16 deep, where a balanced split would be about 6 deep and n log₂ n is 160. Halve the length to 16 and the count is 88; doubling n multiplied the work by 3.45.
A count that roughly quadruples when n doubles is behaving quadratically and a count that roughly doubles is not, and the lab prints the ratio at two sizes rather than reading a verdict off a curve. Two sizes are two measurements. The n log₂ n and n(n − 1)/2 lines on the plot are drawings sampled at double precision; every verdict on the panel compares integers.
Two further readings from the same panel are worth having. First, rule-specificity: the array built against median of three costs a first-element pivot 143 comparisons, and the array built against a first-element pivot costs a middle-element pivot 103. Each rule has its own bad input, which is exactly what it means for the flaw to be in the rule rather than in quicksort. Second, the array of 24 equal keys: every rule pays 276 there, n(n − 1)/2 again, because Lomuto sends every key equal to the pivot to one side.
So what is quicksort's cost? On the input in front of you, whatever the lab measured. As a claim about all inputs under a deterministic rule, Θ(n²), because the killer exists. “Randomised Quicksort” changes the question by changing where the randomness lives, and gets an answer that is exact and holds on every input at once.
Interactive
Choose a rule, then meet the array built to defeat it
Method
Do not ask how fast the rule is. Ask which inputs it is betting against, and then look for one.
Put your guess for k into T(n) = T(k) + T(n − k − 1) + (n − 1) and solve it. This is where a claim becomes falsifiable: a rule that promises k ≈ n/2 is promising something about every input, and one input is enough to test it.
Sorted, reverse sorted, up-then-down, all keys equal. A first-element pivot fails on the first two immediately, at 496 comparisons for 32 keys. A rule that survives these has only survived four families.
Choose the killer order and watch the count and the depth. The array is a permutation of 1 … n, the sort still returns the sorted array, and the cost is quadratic: the bad case is exhibited rather than asserted.
Halve n and compare. About four times the work means quadratic behaviour on this family; about twice means n log n behaviour on this family. Neither is a proof, and the word to use out loud is “on this family”.
The table's footer prints merge sort's comparison count on the same array, from an implementation written for another course, and the panel prints ⌈log₂ n!⌉. One is an independent measurement and the other is a bound on every comparison sort; a measured count above both is a cost, not a contradiction.
Set the pivot rule to median of first, middle and last, the input order to the array built to kill this rule, and the length to 32. The array below is what the lab constructs, and the call table is the first eight partitions of the run it then measures.
Every left side is empty. That is the signature: the rule's three candidates have been arranged so that their median is always the smallest key left, so k = 0 at every call and the recurrence degenerates to T(n) = T(n − 1) + (n − 1). The depth is 16 rather than 31 because the adversary only has to fool the rule on the first half of the array; after that the tail is already arranged.
The measured 304 is below n(n − 1)/2 = 496, and the difference is the three comparisons per call the median-of-three rule spends on its own decision, plus the shape of the tail. So the measurement is not the recurrence's worst case exactly; it is quadratic behaviour on a real input, which is what was to be shown.
For a faded rehearsal, keep the killer order and change the rule to a seeded random pivot. The supplied first move: the array is rebuilt, because the killer is a function of the rule, and for a randomised rule the lab builds the median-of-three killer instead. Predict what happens to the count before you look, then move the seed slider and watch the count move while nothing else does — that is “Randomised Quicksort” in one control.
You should be able to write the recurrence for a given split, say what k = 0 at every call costs, explain how the lab builds an input against a rule, and state what a count at two sizes does and does not establish.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.