Re: Wrong info in libc comparison

[Markus Wichmann <nullplan@gmx.net>]

On Sat, Sep 16, 2017 at 12:18:02PM -0400, Rich Felker wrote:
> Even non-naive quicksort has O(n²) time; there is a way to avoid this
> with an esoteric efficient algorithm for finding the median to use as
> the pivot, but nobody does it because the constant is so bad. The only
> known practical way to avoid the n² worst-case is some kind of
> introsort. So "naive" is really only about the problem of blowing up
> the stack.
> 

Oh crap, yes, I forgot about that. Median-of-three only solves the
quadratic time problem on sorted inputs but quadratic sequences still
exist. My bad.

> I agree something like "mergesort+quicksort" sounds good, but just to
> make sure, was mergesort already in use in the glibc version in the
> comparison? i.e. can I make this fix without inconsistently reflecting
> information from different glibc versions?
> 
> Rich

Yes, I previously looked at glibc 2.19 and it had the same code.

Apparently, the files are really old with only minor changes over the
years. At least, that's what I gathered from the changelogs.

Ciao,
Markus