From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 10356 invoked from network); 9 Feb 2023 19:21:01 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 9 Feb 2023 19:21:01 -0000 Received: (qmail 18302 invoked by uid 550); 9 Feb 2023 19:20:58 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 18268 invoked from network); 9 Feb 2023 19:20:58 -0000 DKIM-Filter: OpenDKIM Filter v2.11.0 mail.ispras.ru 531D04077B1C Date: Thu, 9 Feb 2023 22:20:45 +0300 (MSK) From: Alexander Monakov To: musl@lists.openwall.com cc: Markus Wichmann In-Reply-To: <20230209190316.GU4163@brightrain.aerifal.cx> Message-ID: <23cd3146-4e39-6549-24ae-7fe7f24bed08@ispras.ru> References: <4d290220.36d6.1860222ca46.Coremail.00107082@163.com> <20230201180115.GB2626@voyager> <20230209190316.GU4163@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Subject: Re: [musl] Re:Re: [musl] 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