Sign in to watch this lesson
Algorithms - Sorting and Searching · 4:34
Quicksort and What std::sort Really Does
We partition [3, 8, 2, 5, 1, 4, 7, 6] around 4 with Hoare's two inward-walking arrows, then break quicksort three ways: sorted input with a first-element pivot, an adversary that defeats median-of-three, and repeated keys, where Lomuto goes quadratic and a three-way partition finishes in one pass. Then we open libc++'s std::sort on this Mac, an introsort with insertion sort for small ranges and a heapsort fallback after 2·log2 n levels, and measure it against the same adversary. Finally, why the comparator must be a strict weak ordering: a <= comparator crashes std::sort here.
You will learn
- Trace Hoare's partition and explain why it splits into a part <= pivot and a part >= pivot
- Explain how sorted input, repeated keys and adversarial input make naive quicksort quadratic, and how median-of-three, Hoare and 3-way partitioning help
- Describe libc++'s introsort (pivot choice, insertion sort below 24 elements, heapsort after 2*floor(log2 n) levels) and why it guarantees O(n log n)
- Write comparators that are strict weak orderings, using std::tie for multi-key sorts