Quicksort & Partition
Quicksort picks a pivot, partitions elements into less-than and greater-than groups, and recursively sorts each partition. Average O(n log n), worst case O(n²).
Quicksort = picking a team captain (pivot), everyone shorter goes left, taller goes right. Then each side picks their own captain and repeats. Bad captain picks (always shortest kid) make it painfully slow.
Lomuto partition: choose last element as pivot, maintain boundary i, swap elements ≤ pivot to left of i. Hoare partition: two pointers from opposite ends, more efficient in practice (3× fewer swaps). Worst case O(n²) occurs on already-sorted input with naive pivot (always picks min/max). Mitigations: random pivot, median-of-three pivot. Quickselect uses the same partition to find k-th smallest in O(n) average.
Three-way partition (Dutch National Flag by Dijkstra) handles duplicates in O(n) instead of O(n log n) for many-duplicate inputs — maintains three regions: <pivot, ==pivot, >pivot. Introsort (used in C++ std::sort) is quicksort that switches to heapsort when recursion depth exceeds 2*log(n), guaranteeing O(n log n) worst case while keeping quicksort's average-case speed. Quicksort is cache-friendly (sequential access) unlike heapsort (random access to heap). In-place quicksort uses O(log n) average stack space (O(n) worst case — mitigated by always recursing on smaller partition first).
Quicksort is average O(n log n) with excellent cache performance — it's usually the fastest comparison sort in practice. The key insight is the partition step: everything less than pivot ends up left, everything greater ends up right, and the pivot is in its final position. I use random or median-of-three pivot to avoid O(n²) worst case. For finding the k-th largest element, quickselect gives O(n) average — I recurse only into the partition containing the k-th element.
Quicksort on a sorted array with last-element pivot selection is O(n²) — the pivot is always the minimum, partitioning reduces size by only 1 each step. Always randomize the pivot or use median-of-three. Also: Lomuto partition with duplicates of the pivot can perform O(n²) — use three-way partition for inputs with many repeated elements.