25 ms·
C's qsort() is notoriously bad because the comparison function isn't inlined, meaning the majority of time is spent in call overhead. Zhangxp1998 ported quadso
by nightcracker 7y ago
C's qsort() is notoriously bad because the comparison function isn't inlined, meaning the majority of time is spent in call overhead.
Zhangxp1998 ported quadsort to C++ and compared with std::sort and found it to be slower: https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0dbf2d862a https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d...
Shameless self promotion, if you want a faster sorting implementation, check out pdqsort (https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort) which is almost twice as fast as libstdc++'s std::sort for randomly shuffled integers, and has all sorts of tricks for input distributions with patterns (like pre-sorted, reverse sorted, single out-of-order element appended, etc).
- vhvjkyhkogvv 7y agoComparing 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.
- 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>