Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 16 Sep 2017 20:38:24 +0200
From: Markus Wichmann <>
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.


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.