...one of the most highly
regarded and expertly designed C++ library projects in the
world. — Herb Sutter and Andrei
Quicksort naturally performs bad on inputs that form patterns, due to it being a partition-based sort. Choosing a bad pivot will result in many comparisons that give little to no progress in the sorting process. If the pattern does not get broken up, this can happen many times in a row. Worse, real world data is filled with these patterns.
Traditionally the solution to this is to randomize the pivot selection
of quicksort. While this technically still allows for a quadratic worst
case, the chances of it happening are astronomically small. Later, in introsort,
pivot selection is kept deterministic, instead switching to the guaranteed
O(n log n) heapsort if the recursion depth becomes too big. In
we adopt a
hybrid approach, (deterministically) shuffling some elements to break up
patterns when we encounter a "bad" partition. If we encounter
too many "bad" partitions we switch to heapsort.