[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 10 Feb 2023 05:10:33 +0100
From: Markus Wichmann <nullplan@....net>
To: musl@...ts.openwall.com
Subject: Re: Re:Re: qsort
On Thu, Feb 09, 2023 at 02:52:45PM -0500, Rich Felker wrote:
> On Thu, Feb 09, 2023 at 10:20:45PM +0300, Alexander Monakov wrote:
> >
> > On Thu, 9 Feb 2023, Rich Felker wrote:
> >
> > > glibc does not use
> > > it by itself, but uses "introsort", a fancy way to say it introspects
> > > the quicksort (rather just counts the depth) and switches to an O(n
> > > log n) algorithm once it's descended too many levels.
> >
> > This is so completely untrue. Glibc uses mergesort, falling back on
> > quicksort with median-of-three pivot selection when allocating the
> > intermediate array for mergesort fails or seems too costly:
>
> Did this change at some point or have I just always been under the
> wrong impression on this?
>
> Rich
The latter. As I recall, I notified you about this because it was also
wrong on the etalabs libc comparison page. Lemme check... yep, still
wrong.
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.
