I wouldn't expect std::sort to be slower than std::stable_sort in general

[dhruvbird]

Also, std::sort should be faster than qsort() since the comparator is usually inlined in the former v/s called via a function pointer in the latter.

[Morwenn]

I have to agree. This is indeed strange. To make sure, I tweaked one of my usual sorting benchmarks so that I could use SqrtSort with it; here are the results:

It sorts vectors of one million integers. I compiled it with g++ -std=c++14 -O3 -march=native. We can see that std::sort is generally faster than std::stable_sort, which is generally faster than std::qsort. In the end, SqrtSort is faster than std::sort for some specific patterns, but still slower for random data. In the end, it mostly depends on the patterns.

[dhruvbird]

@Morwenn Your results sound about right for random data (which in this case is the "shuffled" case?)

Please could you link me to the benchmark you ran so that I can understand what each of the sorting patterns mean, and what "vergesort" means.
Thanks!

[Morwenn]

@dhruvbird The vergesort is actually a sorting algorithm I developped a few weeks ago, even though it's a mere wrapper around a pattern-defeating quicksort designed to be more efficient in a few specific cases and almost as fast otherwise. You can find the benchmarks in its benchmark directory. I had to tweak them a bit to make them work with SqrtSort but they remain the same in essence.

The pattern-defeating quicksort is a general-purpose sorting algorithm designed to replace the current implementations of std::sort; it's a fast O(n log n) unstable in-place algorithm that uses O(1) auxilliary memory. It is considered for inclusion into libstdc++ and libc++.

[dhruvbird]

@Morwenn Thanks for the pointers!