[nneonneo]

I would love to see the benchmark results against Timsort, the Python sorting algorithm that also implements a bunch of pragmatic heuristics for pattern sorting. Timsort has a slight advantage over pdqsort in that Timsort is stable, whereas pdqsort is not.

I see that timsort.h is in the benchmark directory, so it seems odd to me that the README doesn't mention the benchmark results.

[orlp]

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 as the cost of a comparison increases.