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
Musser's introsort.