Skip to interview prep
Apexed

267. What inputs make quicksort quadratic, and how do pivot strategies (first element, median, median-of-three, random) help?

MediumSorting

Technical
Show model answer

Quicksort is O(n²) whenever partitions are consistently lopsided. With the first (or last) element as pivot, already sorted and reverse-sorted arrays are the worst case, since each partition peels off just one element. Arrays with many equal keys are also quadratic for a two-way partition that puts all equal keys on one side; three-way partitioning fixes that.

Choosing the exact median (via median of medians) guarantees O(n log n) worst case, but the linear-time selection has large constants, so it is rarely used. Median-of-three is cheap and defeats sorted input, but crafted "killer" inputs still exist. A random pivot makes the expected time O(n log n) for every input, because the bad case now depends on coin flips rather than on the data.

Production sorts such as introsort start with quicksort and switch to heap sort when recursion gets too deep, giving a hard O(n log n) bound while keeping quicksort’s speed.

What interviewers listen for

  • Recurse into the smaller side first to bound stack depth at O(log n)
What inputs make quicksort quadratic, and how do pivot strategies (first element, median, median-of-three, random) help — Data structures & algorithms interview