Comment by chrka

As for your party trick: The performance drop in "blqs" occurred because heapsort was applied directly to a poorly partitioned input. Quicksort now gets a second chance in this case. With 10% random, 90% sorted, the performance drop no longer occurs. It is now faster than std::sort.