[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20170916183824.6i6m2chfwgyvslzp@voyager>
Date: Sat, 16 Sep 2017 20:38:24 +0200
From: Markus Wichmann <nullplan@....net>
To: musl@...ts.openwall.com
Subject: Re: Wrong info in libc comparison
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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
