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

The Worst Case

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 pdqsort 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.


PrevUpHomeNext