The worst case is not a rare accident
Set Pivot to “first element”, Input to “already sorted”, and press Skip to end. The comparison count lands exactly on n(n−1)/2 — every possible pair compared, which is what bubble sort does.
Running this on 2,000 elements and counting comparisons rather than seconds — so that the measurement is about the algorithm and not about which language it was written in — gives:
| Input (2,000 elements) | Comparisons, first-element pivot |
|---|---|
| Random | 26,419 |
| Already sorted | 1,999,000 |
| Reverse sorted | 1,999,000 |
| Nearly sorted | 658,602 |
| Many duplicates | 206,154 |
Changing nothing but the order of the input makes it 76 times slower, and 1,999,000 is not merely “similar to” bubble sort — in the same measurement bubble sort and selection sort produced that identical number, because 2000 × 1999 ÷ 2 = 1,999,000 is what comparing every pair costs. Quicksort’s reputation for speed is a statement about random input, and sorted input is not a weird edge case; it is the single most likely thing to be handed to a sort routine in real code. Full measurements, eight algorithms.
Why sorted input is the bad case
Quicksort is fast when the pivot splits the array roughly in half, because halving repeatedly reaches size 1 after about log₂n rounds. If the pivot is the first element of an already sorted array, it is also the smallest element — so one side of the partition gets nothing and the other gets everything but one. The array shrinks by one per round instead of halving, giving n rounds of n comparisons instead of log₂n of them. Watch the recursion depth readout: it climbs to n−1 instead of stopping near log₂n.
What the pivot rules fix, and what they do not
Middle element and median of three both defeat the sorted-input case specifically, which is why they are what real libraries use — but an adversary who knows the rule can still construct an input that defeats them. Random element is the only rule with no bad input at all, because there is no input to construct against: the expected comparison count is about 1.39 n log₂ n regardless of what you feed it. In the 2,000-element measurement the random pivot stayed near 25,000 comparisons on every input type — except one.
Duplicates are a separate problem
Set Input to “many duplicates” and try the random pivot. It does not help much: on the 2,000-element run it still took 205,154 comparisons, eight times its usual figure. Elements equal to the pivot keep getting shuffled around instead of being finished with. The fix is a different partition entirely — three-way partitioning, which separates “less”, “equal” and “greater” and never recurses into the equal group. On the same input that dropped to 10,000 comparisons, twenty times faster.
Lomuto and Hoare are not the same algorithm
Switch Partition and the comparison count changes on the same array with the same pivot. Lomuto scans once from left to right and always performs exactly hi − lo comparisons per call; it is the version in most textbooks because it is short. Hoare walks two pointers inward until they cross, does about three times fewer swaps, and is what real implementations derive from — but its pivot ends up somewhere in the middle rather than at a known index, so the recursion is written differently. Both are shown here because “quicksort” in a homework question usually means one specific one of them.
One warning if you are implementing Hoare yourself: taking a[hi] as the pivot value breaks it. The two pointers can both stop at hi, the function returns hi, and the recursive call gets handed the identical range it started with — an infinite loop, not a slow sort. The usual fix, and the one this page uses, is to move the chosen element to lo before scanning, which makes every pivot rule safe. Lomuto has the mirror-image convention: it moves the pivot to hi. Mixing up which convention goes with which scheme is the most common way this algorithm is got wrong.