[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20230209201814.GW4163@brightrain.aerifal.cx>
Date: Thu, 9 Feb 2023 15:18:14 -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 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?
To self-answer, from git history it looks like I was just completely
wrong. Maybe it was GNU libstdc++ using introsort? Or..?
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.
