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

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.



Applications are open for YC Summer 2020

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

Search: