Quick Sort Pivot Selection Strategies

Quick Sort's cost is the depth of its recursion multiplied by the O(n) work done at each level.

A pivot near the median splits n into two halves. Halving repeatedly reaches size 1 after about log₂n levels, so 1,000,000 elements need about 20 levels: 20 × n work, i.e. O(n log n).

A pivot that is the smallest or largest element splits n into a part of size 0 and a part of size n−1. Now you need n levels, giving n × n work: O(n²). For 1,000,000 elements that is roughly a trillion operations instead of 20 million — a fifty-thousand-fold difference produced by nothing but pivot choice.

Reassuringly, the split does not have to be good, only not-catastrophic. Even a consistent 90/10 split still yields O(n log n), just with a larger constant, because reducing the problem to 90% of its size repeatedly still takes a logarithmic number of steps. The pivot rule only needs to make the terrible case unlikely, not guarantee the perfect one.

The simplest rule, used in nearly every textbook because it makes the partition code short: take A[hi] as the pivot.

procedure partition(A, lo, hi):
  pivot = A[hi]            // last element
  i = lo - 1
  for j = lo to hi - 1:
    if A[j] <= pivot:
      i = i + 1
      swap(A[i], A[j])
  swap(A[i + 1], A[hi])
  return i + 1

Its failure is severe and its trigger is embarrassing. On an already-sorted array the last element is the maximum, so everything goes to the left partition and nothing to the right: O(n²). The same happens on a reverse-sorted array.

This matters because sorted or nearly-sorted input is extremely common — data straight out of a database with an ORDER BY, a list being re-sorted after a couple of appends, timestamps. The naive pivot is worst precisely where real data most often lives. Never ship it.

Pick a uniformly random index in the range and swap it to the end, then partition as usual:

procedure quickSort(A, lo, hi):
  if lo < hi:
    r = random integer in [lo, hi]
    swap(A[r], A[hi])          // randomised pivot
    p = partition(A, lo, hi)
    quickSort(A, lo, p - 1)
    quickSort(A, p + 1, hi)

This is a genuine fix, and the reason is subtle but important: the worst case no longer belongs to any particular input. With a fixed rule, an adversary (or an unlucky data source) can hand you the one array that breaks it. With randomisation, no input is bad — only an unlucky sequence of coin flips is, and the probability of enough consecutive bad flips to matter is astronomically small. Expected time is O(n log n) for every input.

It is not free: generating random numbers costs something, and the branch is unpredictable. But it is the standard defence, and it is the answer interviewers are usually looking for.

Look at the first, middle and last elements, take the median of those three, and use it as the pivot.

procedure medianOfThree(A, lo, hi):
  mid = lo + (hi - lo) / 2
  // order the three positions, then use the middle one
  if A[lo] > A[mid]:  swap(A[lo], A[mid])
  if A[lo] > A[hi]:   swap(A[lo], A[hi])
  if A[mid] > A[hi]:  swap(A[mid], A[hi])
  return mid                    // A[mid] is the median

This is the best practical heuristic without randomness, and it has a very useful property: on sorted input the middle element is the true median, so the pathological case for the naive pivot becomes the best case here. Since sorted-ish data is the common real-world hazard, median-of-three removes most of the risk for free, with no random number generator and better branch behaviour.

Its limitation is that it remains deterministic, so a determined adversary can still construct a killer input (there is a known "median-of-three killer" sequence). For sorting untrusted, attacker-controlled data, prefer randomisation or a depth limit. For ordinary data, median-of-three is excellent. Larger implementations extend the idea — sampling five or nine elements, or the "ninther" (median of three medians of three) — as arrays get bigger.

Two refinements change the partition itself rather than the pivot choice.

Dual-pivot Quick Sort (Vladimir Yaroslavskiy, 2009) picks two pivots and splits into three regions: less than P1, between P1 and P2, and greater than P2. Fewer levels of recursion and better cache behaviour make it measurably faster on real hardware, which is why Java uses it for Arrays.sort() on primitive arrays.

Three-way partitioning (the Dutch national flag partition) solves a different problem: many duplicate keys. Standard two-way partitioning puts elements equal to the pivot on one side and then recurses over them again, so an array of all-identical values degenerates to O(n²). Three-way partitioning separates elements into less than, equal to and greater than, and never recurses into the equal block — because those elements are already in their final positions. On data with few distinct values this turns a quadratic disaster into something close to linear.

This is worth remembering, because duplicate-heavy data is very common: sorting a million records by a status field with eight possible values will hit it immediately. (Though as the decision guide notes, that particular shape is also Counting Sort's ideal case.)

Real libraries combine defences rather than relying on one.

• C++ std::sort uses Introsort: median-of-three-style pivoting, plus a recursion-depth counter. If depth exceeds roughly 2·log n, it stops trusting the pivots entirely and switches that sub-problem to Heap Sort, which converts a possible O(n²) into a guaranteed O(n log n).
• Java uses dual-pivot Quick Sort for primitives, with introspective checks for structured input, and stable Tim Sort for objects.
• Rust's sort_unstable uses pattern-defeating quicksort (pdqsort), which detects patterns such as already-sorted or many-duplicate input and adapts, falling back to Heap Sort when it detects adversarial behaviour.

The shared design idea is the one worth taking away: do not try to pick a pivot that can never be bad — detect that things are going badly and change strategy. A cheap runtime check plus a fallback is more robust than any amount of cleverness in the pivot rule.

To see the effect directly, open the visualiser, run Quick Sort on a random array and watch the comparison counter, then run it on an already-sorted array. The difference in the counter is the pivot problem.