4 ms·
Mergesort would be a poor choice for qsort() due to the linear space complexity. With N bytes of RAM, you'd only be able to sort (a bit less than) N/2 bytes of
by matslina 12y ago
Mergesort would be a poor choice for qsort() due to the linear space complexity. With N bytes of RAM, you'd only be able to sort (a bit less than) N/2 bytes of data. An in-place algorithm is preferable.
Glibc is the only libc I'm aware of that implements mergesort. It still falls back to quicksort for large inputs though.
- mzs 12y agoI just heard about smoothsort: http://code.google.com/p/combsortcs2p-and-other-sorting-algorithms/wiki/SmoothSort http://code.google.com/p/combsortcs2p-and-other-sorting-algo... Also, nice little write-up, thanks. I also dig the extracted sort implementations you dug-out: https://github.com/matslina/qsort https://github.com/matslina/qsort
- tedunangst 12y agoAll BSD derived libcs contains mergesort(), and heapsort() as well.
- mzs 12y agoTrue, but parent meant used in the qsort and qsort_r implementations.
- tedunangst 12y agoOh, of course. reading fail.