Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20230209195245.GV4163@brightrain.aerifal.cx>
Date: Thu, 9 Feb 2023 14:52:45 -0500
From: Rich Felker <dalias@...c.org>
To: Alexander Monakov <amonakov@...ras.ru>
Cc: musl@...ts.openwall.com, Markus Wichmann <nullplan@....net>
Subject: Re: Re:Re: qsort

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

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.