...one of the most highly
regarded and expertly designed C++ library projects in the
world. — Herb Sutter and Andrei
Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns. pdqsort is an extension and improvement of David Mussers introsort. It is identical in usage to std::sort.