Re: Wrong info in libc comparison

[Rich Felker <dalias@libc.org>]

On Wed, Sep 13, 2017 at 09:25:29PM +0200, Szabolcs Nagy wrote:
> * 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.

If you're considering big-O, where n->infinity (or at least to the
largest value that can fit in memory), malloc most certainly has
failed (because the array to be sorted already filled memory) and
you're looking at the "fallback" case.

Maybe the comparison of sort algorithm used is interesting for reasons
other than just big-O though, in which case mentioning the "merge
(when it fits in memory)" would probably be helpful.

Rich