[matslina]

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]

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

[tedunangst]

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

[mzs]

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

[tedunangst]

Oh, of course. reading fail.