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