Even on random data, 50% of the time you'll pick a bad pivot. Get a slightly unlucky run and you're into quadratic behavior for that subset; the more data you're sorting, the more likely introsort's switch to heapsort on deep recursion (and insertion sort on small ranges) will help.
qsort: 39 mergesort: 39 qsort: 38 mergesort: 40 qsort: 37 mergesort: 39 qsort: 38 mergesort: 40 qsort: 38 mergesort: 40 qsort: 38 mergesort: 40 qsort: 38 mergesort: 39
Could you perhaps post a quick description, and the gains you were seeing? I'm interested because if it isn't too hard it could always be ported into g++ / clang's libc++.
Basically I wrote each sort block as individual functors (partitioning, merging). You run that through a filter stack that decides what to do depending on the input size and the current recursion depth.
It's faster (I think) because when the recursion depth is a compile-time value, the compiler can unroll the recursion.
It's old code I wrote for Boost but never had the time to finish & submit. As I quickly read through it there's a couple of rough edges to polish.
What was surprising is that in hinting the compiler through template hacking I was able to squeeze a little more speed out of introsort (If you're interested: https://github.com/flexsortea/flex_sort).