cpp-TimSort

There are multiple reasons I don't include Timsort in my README benchmark graph: 1. There is no authoritative implementation of Timsort in C++. In the bench directory I included https://github.com/gfx/cpp-TimSort, but I don't know the quality of that implementation. 2. pdqsort intends to be the algorithm of choice of a system unstable sort. In other words, a direct replacement for introsort for std::sort. So std::sort is my main comparison vehicle, and anything else is more or less a distraction. The only reason I included std::stable_sort in the benchmark is to show that unstable sorting is an advantage for speed for those unaware. But, since you're curious, here's the benchmark result with Timsort included on my machine: http://i.imgur.com/tSdS3Y0.png This is for sorting integers however, I expect Timsort to become substantially better

I'm sorry, the profiling code for timsort wasn't included in my remote repository yet. I profiled against https://github.com/gfx/cpp-TimSort . Also, C++ has always had the "top-n" interface called partial sort: http://en.cppreference.com/w/cpp/algorithm/partial_sort .

I've ported Java's timsort to C++: https://github.com/gfx/cpp-TimSort and concluded that it can be useful for scripting languages like Python but not so useful for C++.