Re: Wrong info in libc comparison

[Szabolcs Nagy <nsz@port70.net>]

* Markus Wichmann <nullplan@gmx.net> [2017-09-13 20:51:06 +0200]:
> 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,

i think malloc failure case is the one that matters
for worst case analysis so the comparision table
should say whatever quicksort is doing.