Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Bad Partitions

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 after partitioning. 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.


PrevUpHomeNext