Hacker News Reader

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.

View on HN

I am sorry, could you explain this in a bit more detail?

Normally, quicksort works best on random data. But with 90% already sorted and 10% random, it actually becomes harder to pick a good pivot. Sometimes the pivot ends up too large, which creates very uneven splits. When that happens, the algorithm switches to heapsort to avoid worst-case behavior, but heapsort is slower. Now, instead of immediately switching, it tries to partition again. Only if it’s still bad does it fall back to heapsort. That’s why performance improves.

Reply on news.ycombinator.com