...one of the most highly
regarded and expertly designed C++ library projects in the
world. — Herb Sutter and Andrei
A bad partition occurs when the position of the pivot after partitioning is under 12.5% (1/8th) percentile or over 87,5% percentile - the partition is highly unbalanced. When this happens we will shuffle four elements at fixed locations for both partitions. This effectively breaks up many patterns. If we encounter more than log(n) bad partitions we will switch to heapsort.
The 1/8th percentile is not chosen arbitrarily. An upper bound of quicksorts worst case runtime can be approximated within a constant factor by the following recurrence:
T(n, p) = n + T(p(n-1), p) + T((1-p)(n-1), p)
Where n is the number of elements, and p is the percentile of the pivot
T(n, 1/2) is the best case for quicksort.
On modern systems heapsort is profiled to be approximately 1.8 to 2 times
as slow as quicksort. Choosing p such that
T(n, 1/2) / T(n, p) ~=
1.9 as n gets big will ensure that we will only switch to heapsort
if it would speed up the sorting. p = 1/8 is a reasonably close value and
is cheap to compute on every platform using a bitshift.