Compare with your guess from step 2.

Shuffled data — all fine

$ algo dc -in s10k.jsonl -order shuffled
n = 10000, order = shuffled

algorithm                   comparisons            moves         wall
merge                            120440           133616        7.5ms
quick (first pivot)              149913            75946      2.005ms
quick (median-of-3)              146520            78217      2.999ms
quick (random)                   156381            89939      2.499ms

All four at ~120–156 thousand comparisons. In lesson 7 the same slice cost insertion sort 24,893,296. That is a 200× difference, and it is the whole reason this lesson exists.

Quicksort makes more comparisons than merge sort and is still faster: it works in place, so it moves less data (75,946 against 133,616).

Sorted data — and there it is

$ algo dc -in s10k.jsonl -order sorted
n = 10000, order = sorted

algorithm                   comparisons            moves         wall
merge                             64608           133616      6.583ms
quick (first pivot)            49995000             9999    325.219ms
quick (median-of-3)              131343            70826          1ms
quick (random)                   159057            89759      2.008ms

49,995,000. Up from 149,913.

That is 333× more comparisons and 162× longer — purely because the data was already tidy.

And the number is familiar: 49,995,000 = n(n−1)/2. Exactly what lesson 7's bubble and selection sorts cost. A quicksort with a first-element pivot, on sorted input, is an elementary sort.

The same -sorted flag that gave insertion sort its best case in lesson 7 gives quicksort its worst here. That is the second of the three payoffs lesson 1 promised.

Merge sort, meanwhile, has an easier time: 64,608 instead of 120,440. It has no bad case — and the test checks that on all three orders.

Fixing the pivot — and where it is not enough

Median-of-three rescues sorted input completely: 131,343 instead of 49,995,000. Three hundred and eighty times better, and even slightly less than on shuffled data.

But run it on reverse-sorted input:

$ algo dc -in s10k.jsonl -order reverse
algorithm                   comparisons            moves         wall
merge                             69008           133616      5.004ms
quick (first pivot)            49995000         25009999    506.951ms
quick (median-of-3)             8379139          4187234     94.662ms
quick (random)                   151569            87173      2.083ms

Median-of-three: 8,379,139. Not 50 million, but not 146 thousand either — 57× more than on shuffled data.

Is it still quadratic growth? Measure at two sizes:

n	median-of-three, reverse	ratio
1,000	86,890	—
10,000	8,379,139	×96

Ten times the n, a hundred times the work. Yes, still quadratic — just with a constant about six times smaller.

The random pivot over the same range: 10,837 → 151,569, a ×14 — which is what O(n log n) growth actually looks like.

Median-of-three fixes the case you thought to check. A random pivot fixes the ones you did not.