HNHacker News
TopNewBestAskShowJobs

zhangxp1998

29 karma · joined November 25, 2019

submissionscomments
zhangxp1998··on Quadsort: a stable non-recursive merge sort
It's just quick sort with insertion sort for small base cases.
zhangxp1998··on Quadsort: a stable non-recursive merge sort
" 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··on Quadsort: a stable non-recursive merge sort
I agree is unfair. The point of my benchmark was that the OP's claim "quad sort is faster than quicksort" is false.
zhangxp1998··on Quadsort: a stable non-recursive merge sort
I looked at disassembly of generated binary, sure, function calls inside quad sort were also inlined.
zhangxp1998··on Quadsort: a stable non-recursive merge sort
See https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... for a comparison of quadsort with C++'s std::sort. The compare functions are inlined.
zhangxp1998··on Quadsort: a stable non-recursive merge sort
qsort has to invoke your comparison function repeatedly, which incurs a lot of overhead. Try C++'s std::sort
zhangxp1998··on Beating C with 70 lines of Go
Okay, so you are comparing single-threaded GNU wc with your multi-threaded Go implementation? That's fair.