Hacker News new | past | comments | ask | show | jobs | submit login

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/0e2fa30656c894017d183e0d...

Shameless self promotion, if you want a faster sorting implementation, check out 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).






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.

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>




Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: