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

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.




I just heard about 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


All BSD derived libcs contains mergesort(), and heapsort() as well.


True, but parent meant used in the qsort and qsort_r implementations.


Oh, of course. reading fail.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: