Quicksort

Quicksort picks a pivot, partitions the array so all smaller elements come before the pivot and all larger come after, then recurses on each side. The partition is in-place — no auxiliary array — making quicksort the typical choice when memory matters.

The partition

Two-pointer scheme (Lomuto): maintain a pointer $i$ to the boundary between "less than pivot" and "rest." Walk pointer $j$ across the array; whenever $A[j] <$ pivot, swap $A[i]$ and $A[j]$ and advance $i$. At the end, swap the pivot into position $i$. $O(n)$, in-place.

Hoare's scheme is another option — slightly more efficient in practice but trickier to get right.

Pivot choice

The pivot determines partition balance. Bad pivots (smallest or largest) give $O(n^2)$ recursion. Common strategies:

• Random pivot: pick a random index. Adversarial input no longer breaks it. Expected $O(n \log n)$.
• Median-of-three: median of first, middle, last. Cheap and robust on real data.
• Median-of-medians: deterministic $O(n)$ pivot selection. Theoretically tight, but constant factors usually outweigh the benefit.

Why $O(n^2)$ worst case

Sorted input plus first-element pivot gives partition sizes 1 and $n - 1$, leading to $n$ levels of recursion each doing $O(n)$ work. Total $O(n^2)$. With random or median-of-three pivoting, this is vanishingly unlikely.

Why so popular anyway

Quicksort's inner loop is extremely cache-friendly. Modern CPUs love sequential access and predictable branches. Even though theoretically equivalent to merge sort, quicksort beats it on real arrays by a meaningful constant factor.

Variants

3-way partition (Dutch national flag) handles many equal keys efficiently: partition into less-than, equal-to, and greater-than the pivot. Recurse only on the unequal sides. Often used in $C$++ std::sort.