Quick Sort Pivot Selection: First vs Random vs Median Benchmarked

The Pivot That Crashed My Mock Interview

Picking the first element as your Quick Sort pivot on a sorted array takes O(n²). Everyone knows this. But I ran a benchmark on 50 different "interview arrays" — already sorted, reverse sorted, duplicates-heavy, nearly sorted with a few swaps — and the performance gaps were wilder than expected. Median-of-three wasn't always the winner.

Here's the thing: most coding interviews don't hand you random data. They hand you edge cases designed to break naive solutions. And your pivot strategy is the difference between a 3ms sort and a stack overflow.

Why Pivot Selection Matters More Than You Think

Quick Sort's average case is $O(n \log n)$, achieved when each pivot divides the array roughly in half. The recurrence relation looks like:

$$T(n) = 2T(n/2) + O(n)$$

But pick the minimum or maximum element as pivot, and you get:

$$T(n) = T(n-1) + O(n) = O(n^2)$$

That's the textbook explanation. In practice, the constant factors matter a lot. Random pivot selection adds overhead from random.randint() calls. Median-of-three requires two extra comparisons per partition. On small arrays (n < 50), these costs can exceed the benefits.

---

Continue reading the full article on TildAlice