Quick sort

Quick sort is a randomized divide-and-conquer sorting algorithm. Pick a pivot element, partition the array into elements less than and greater than the pivot, then recurse on each partition. Average $O (n lo g n)$ , in-place, and consistently fast on real data — making it the most widely-used general-purpose sort.

The structure:

Divide: pick a pivot $x$ . Partition the array into three groups: less than $x$ (L), equal to $x$ (E), greater than $x$ (G).
Conquer (recur): sort L and G recursively.
Combine: concatenate L, E, G — the array is now sorted.

The “equal” group (E) is just the pivot itself; you don’t need to recurse on it.

Implementation

There are two clean partition schemes — both correct, both with their own atomic notes.

Lomuto partition — single boundary pointer, simpler invariants. Pivot ends at the returned index. About $n /2$ swaps per partition. The version most students see first.
Hoare partition — two pointers walking inward. Returned index is not the pivot’s position. About $n /6$ swaps per partition. Handles duplicates much better. Tony Hoare’s original.

Both partition schemes are subroutines of quicksort: pick a pivot, partition, recurse on each side. The recursive set-up differs:

// With Lomuto: pivot is at p, exclude it from both sides
quicksort(arr, lo, p - 1);
quicksort(arr, p + 1, hi);
 
// With Hoare: returned index is a split point, not a position
quicksort_hoare(arr, lo, p);       // includes p
quicksort_hoare(arr, p + 1, hi);

Mixing up the recursion form is the classic Hoare-implementation bug. See Hoare partition for the worked-trace and Lomuto partition for the simpler version with full code.

Big O

Best case: $O (n lo g n)$ — pivot always lands in the middle, so each recursive call halves the problem. Recursion depth is $lo g n$ , work per level is $n$ .
Average case: $O (n lo g n)$ — for random pivot choices on random data.
Worst case: $O (n^{2})$ — pivot always lands at one extreme (e.g., always picking the first element on already-sorted input). Recursion depth becomes $n$ .

The worst case is a real concern. Mitigations:

Randomize the pivot: pick a random index instead of always the first. Adversarial inputs become unlikely.
Median of three: take the median of arr[first], arr[mid], arr[last] as the pivot. Avoids worst-case behavior on common patterns (sorted, reverse-sorted).
Switch to heap sort on deep recursion: introsort uses quicksort but switches to heap sort once recursion depth exceeds about $2 lo g_{2} n$ — guaranteed $O (n lo g n)$ worst case.

Why it’s fast in practice

Despite the $O (n^{2})$ worst case, quicksort beats merge sort and heap sort on real workloads. Reasons:

Cache friendly: in-place partition keeps data contiguous in memory.
Few swaps: typical partition does fewer swaps than other sorts.
Tail call elimination: the second recursive call can be done iteratively, saving stack frames.

Real-world sorting (C qsort, C++ std::sort, Python sort for primitives, Java Arrays.sort for primitives) is almost always quicksort or a variant.

In-place

Quicksort uses $O (lo g n)$ extra space (for the recursion stack). The array itself is sorted in place — no auxiliary array needed, unlike Merge sort which needs $O (n)$ extra.

Stability

Quicksort is not stable — swaps during partition can change the relative order of equal elements. If stability is needed, Merge sort is the standard choice.

Comparison with other O(n log n) sorts

Sort	Average	Worst	Space	Stable
Merge sort	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	Yes
Heap sort	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	No
Quick sort	$O (n lo g n)$	$O (n^{2})$	$O (lo g n)$	No

Quick sort dominates when memory matters and worst case isn’t a hard requirement. Merge sort wins for stability and guaranteed worst case. Heap sort is the choice for guaranteed worst case + $O (1)$ space.

For divide-and-conquer with deterministic worst case, see Merge sort. For the simpler quadratic sorts, see Selection sort and Bubble sort.

Idriss Rami — Notes

Explorer