libstdc++'s std::sort doesn't implement quicksort per se. It implements introsort[1]. I'm curious how a pure C implementation of introsort would fare against std::sort.
" It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertionsort when the number of elements is below some threshold. "
You forgot about heapsort. It's a combination of three sorting algorithms, not two. However trivial the difference may seem, I'd still prefer to look at a "C introsort vs C++ introsort" benchmark than a "C quicksort vs C++ often quicksort, but not really" benchmark.
Comments
Comparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.
That is a fair point, I missed that quadsort is claimed to be stable.
I agree is unfair. The point of my benchmark was that the OP's claim "quad sort is faster than quicksort" is false.
libstdc++'s std::sort doesn't implement quicksort per se. It implements introsort[1]. I'm curious how a pure C implementation of introsort would fare against std::sort.
[1]: <https://en.wikipedia.org/wiki/Introsort>
" It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertionsort when the number of elements is below some threshold. "
It's just quick sort with insertion sort for small base cases.
You forgot about heapsort. It's a combination of three sorting algorithms, not two. However trivial the difference may seem, I'd still prefer to look at a "C introsort vs C++ introsort" benchmark than a "C quicksort vs C++ often quicksort, but not really" benchmark.
Too late to edit but I read the article again and they compares it favorably to qsort so it makes sense to point out it's worse than std sort.