4 ms·
Comparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.
by vhvjkyhkogvv 7y ago
Comparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.
- nightcracker 7y agoThat is a fair point, I missed that quadsort is claimed to be stable.
- vhvjkyhkogvv 7y agoToo 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.
- zhangxp1998 7y agoI agree is unfair. The point of my benchmark was that the OP's claim "quad sort is faster than quicksort" is false.
- abjKT26nO8 7y agolibstdc++'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> https://en.wikipedia.org/wiki/Introsort>
- zhangxp1998 7y ago" 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. "
- zhangxp1998 7y agoIt's just quick sort with insertion sort for small base cases.
- abjKT26nO8 7y agoYou 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.