Engineering a Sort Function (1993) [pdf]

If you're interested in these types of implementation/optimization details, Andrei Alexandrescu gave a great talk at this year's CppCon about practical sorting, e.g. when to break out of quicksort to something else: https://www.youtube.com/watch?v=FJJTYQYB1JQ

Thanks for this recommendation. It pushed me to finally watch it and I found it to be a really nice talk.

Really cool to see an "old-school" analysis of a classic algorithm and it's implementation. Today with all of the "advanced features" provided by languages and libraries, it's easy to get lost in minutiae and implementation details; for example, how C++ uses templates to specialize sorts for different types. It's refreshing to see a clean, well-thought-out implementation of a core algorithm and a careful examination of the various trade-offs it represents.

This is totally unrelated but the pdf does not show correctly on my chrome browser (linux), with letters running everywhere. It looks right in evince after download.