pdqsort

https://github.com/orlp/pdqsort

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. All code is available for free under the zlib license.

noticed it because go will be using it in the next release. Note that this makes the default sort unstable! It was previously not guaranteed to be stable, but was in practice

news.yc comments here

here's a youtube talk from the author that I have not watched