Comment on Quadsort: a stable non-recursive merge sortComments−zhangxp19986yqsort has to invoke your comparison function repeatedly, which incurs a lot of overhead. Try C++'s std::sort−zhangxp19986ySee https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... for a comparison of quadsort with C++'s std::sort. The compare functions are inlined.−thedance6yThanks for saving us the time. The punch line: Summarize: Slower than std::sort except on random tail. Also a very important tidbit that std::sort is 10x faster than c's qsort for ordered inputs.−alexchamberlain6yThis feels a little unfair; the function is invoked the same number of times, but C++ has a mechanism for removing the overhead of calling a function (inlining).−zhangxp19986yI looked at disassembly of generated binary, sure, function calls inside quad sort were also inlined.
Comments
qsort has to invoke your comparison function repeatedly, which incurs a lot of overhead. Try C++'s std::sort
See https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... for a comparison of quadsort with C++'s std::sort. The compare functions are inlined.
Thanks for saving us the time. The punch line:
Also a very important tidbit that std::sort is 10x faster than c's qsort for ordered inputs.This feels a little unfair; the function is invoked the same number of times, but C++ has a mechanism for removing the overhead of calling a function (inlining).
I looked at disassembly of generated binary, sure, function calls inside quad sort were also inlined.