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.