[<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.
