[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <23cd3146-4e39-6549-24ae-7fe7f24bed08@ispras.ru>
Date: Thu, 9 Feb 2023 22:20:45 +0300 (MSK)
From: Alexander Monakov <amonakov@...ras.ru>
To: musl@...ts.openwall.com
cc: Markus Wichmann <nullplan@....net>
Subject: Re: Re:Re: qsort
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:
https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/msort.c;h=6dd1cc3aa152d0be99e578c8b4853976451057a5;hb=HEAD
https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/qsort.c;h=728a0ed370e00a76bdd22c3317a75b9be6736f48;hb=HEAD
Alexander
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.
