← Back to the sorting page
Quicksort & Partitioning
Partition around a pivot, recurse on both sides. Fastest comparison sort in practice thanks to cache behavior — and partitioning alone powers Quickselect.
What to know
- Random or median-of-three pivots make the O(n²) worst case vanishingly rare.
- Three-way (Dutch flag) partitioning handles massive duplicate runs in O(n).
- Not stable; introsort falls back to heapsort past a depth limit to cap the worst case.
- Quickselect finds the kth element in expected O(n) — no full sort needed.
In the wild: C stdlib qsort, C++ std::sort core, median/percentile computations.
Algorithms to reach for
Quicksort (Hoare/Lomuto)
O(n log n) avgGeneral in-place sorting
Quickselect
O(n) expectedKth largest without sorting (LeetCode 215)
Three-way partition
O(n)Sort with many duplicate keys
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.