Quicksort: Analysis

Worst Case: $\Theta(n^2)$

The worst case occurs when the pivot is always the minimum or maximum element of the subarray, producing a split of $0$ and $n-1$ elements. This happens, infamously, when the input is already sorted (or reverse-sorted) with a naive first/last-element pivot choice.

Recurrence:

$T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n)$

Using the substitution method:

$T(n) = T(n-1) + kn = (T(n-2) + k(n-1)) + kn = \dots = \Theta(1) + k\sum_{i=1}^{n} i = \Theta(n^2)$

Even a constant-sized split-off (e.g. consistently producing a subarray of size $x$ and $n-x-1$ for constant $x$) still yields $\Theta(n^2)$, because the recurrence becomes $T(n) = T(n-c) + \Theta(n)$.

Best Case: $\Theta(n \log n)$

If the pivot always splits the array exactly in half:

$T(n) = 2T(n/2) + \Theta(n)$

By the Master Theorem (Case 2, $a=2, b=2, f(n)=\Theta(n) = \Theta(n^{\log_2 2})$):

$T(n) = \Theta(n \log n)$

Ratio Splits Also Give $\Theta(n \log n)$

A split of $1/4$ to $3/4$ still produces $\Theta(n \log n)$. The recursion tree has depth $\log_{4/3} n$ on the longest path and $\log_4 n$ on the shortest, with at most $kn$ work per level. In both cases:

$T(n) \le kn \cdot \log_{4/3} n = \Theta(n \log n)$

An ratio split (any constant fraction on both sides, no matter how unbalanced) guarantees $\Theta(n \log n)$. Only constant-sized splits degrade to $\Theta(n^2)$.

Average Case: $\Theta(n \log n)$

Assuming random pivot selection (all permutations equally likely), the expected number of comparisons is approximately $2n \ln n \approx 1.39 \, n \log_2 n$.

Intuition: any two elements $z_i$ and $z_j$ (with $i < j$ in sorted order) are compared if and only if one of them is chosen as a pivot before any element between them in sorted order. The probability they are compared is $\frac{2}{j-i+1}$. Summing over all pairs:

$\mathbb{E}[\text{comparisons}] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1} = \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} \frac{2}{k} \le 2n \sum_{k=1}^{n} \frac{1}{k} \approx 2n \ln n + O(n)$

Thus the expected running time is $\Theta(n \log n)$.

Comparison with MergeSort

Property	Quicksort	MergeSort
Worst case	$\Theta(n^2)$	$\Theta(n \log n)$
Average case	$\Theta(n \log n)$	$\Theta(n \log n)$
Extra space	$O(\log n)$ (stack)	$\Theta(n)$ (merge arrays)
Stable	No	Yes
Cache behaviour	Excellent (in-place, sequential access)	Good but external merge requires extra memory

Despite the $\Theta(n^2)$ worst case, Quicksort is often faster than MergeSort in practice because of low constant factors and cache-friendly memory access patterns. The worst case can be mitigated by random pivot selection or median-of-three.

Summary

Case	Running Time	Condition
Best	$\Theta(n \log n)$	Pivot always splits evenly
Average	$\Theta(n \log n)$	Random pivot; expected ${\sim}2n \ln n$ comparisons
Worst	$\Theta(n^2)$	Pivot always min or max
Ratio split	$\Theta(n \log n)$	Any constant fraction split
Constant split	$\Theta(n^2)$	Splitting off constant-size chunk
Key insight	Unbalanced but proportional splits are fine; constant-remainder splits are disastrous