Median-Pivot Quicksort Recurrence

Intuition. Quicksort's cost is governed by how balanced each partition is. If a median-finding routine of cost $f(n)$ is used to choose the pivot, every split produces two halves of size $n/2$ — the best possible recursion tree of depth exactly $\log n$.

Method. Each recursive call on a subarray of size $m$ does two things, then recurses on two halves:

• find the median in $f(m)$ to use as the pivot,
• partition around it in $\Theta(m)$.

This gives the recurrence

$T(n) = 2\,T(n/2) + f(n) + \Theta(n).$

Since a median needs to read all elements, $f(n)=\Omega(n)$. Per level the partition work sums to $\Theta(n)$ and the median work to $O(f(n))$, so each of the $\log n$ levels costs $O(n+f(n))$. Multiplying:

$T(n) = O\big((n+f(n))\log n\big).$

Worked check. If $f(n)=\Theta(n)$ (linear median, e.g. median-of-medians), then $T(n)=O((n+n)\log n)=O(n\log n)$ — the optimal comparison-sort bound. If $f(n)=n^2$, then $T(n)=O(n^2\log n)$.

T(n) = 2*T(n/2) + f(n) + c*n
     levels: log n   (perfect halving)
     per level: O(n + f(n))
  => O((n + f(n)) * log n)

Pitfall: Do not multiply $n$ by $f(n)$. The median is computed once per recursive call, not once per element; the $n$ (partition) and $f(n)$ (median) costs are added at each level, and the $\log n$ comes from the number of levels.