Re: Wrong info in libc comparison

[Markus Wichmann <nullplan@gmx.net>]

On Wed, Sep 13, 2017 at 02:10:10PM -0400, Rich Felker wrote:
> I'm not sure we agree on what introsort means -- normally I take it to
> mean doing an O(n²) algorithm with good "typical case" performance to
> begin with, but switching to an O(log n) algorithm with a worse
> constant factor as soon as it detects a risk that time will grow
> quadratically. Normally this is something like starting with quicksort
> and possibly switching to heapsort, and my understanding at the time
> was that glibc was doing that or something similar, and AFAIK it still
> is in the general case where there's insufficient memory for a merge
> sort. Does that sound incorrect?
> 
> Rich

At least the version I was looking at (2.19) doesn't do that at all. As
I said, even in case of failed malloc(), all it does is a quicksort.
With an insertion sort afterwards, but that's not introsort by either of
our definitions. And in any case, malloc() failure is rare these days,
so the main algorithm is merge sort.

I just checked the version Debian is currently distributing (2.24) and
saw that nothing major has changed. stdlib/msort.c contains the merge
sort algorithm, and stdlib/qsort.c contains the quicksort fallback, for
your perusal.

Ciao,
Markus