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 14115 invoked from network); 9 Feb 2023 19:53:01 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 9 Feb 2023 19:53:01 -0000 Received: (qmail 13854 invoked by uid 550); 9 Feb 2023 19:52: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 13821 invoked from network); 9 Feb 2023 19:52:57 -0000 Date: Thu, 9 Feb 2023 14:52:45 -0500 From: Rich Felker To: Alexander Monakov Cc: musl@lists.openwall.com, Markus Wichmann Message-ID: <20230209195245.GV4163@brightrain.aerifal.cx> References: <4d290220.36d6.1860222ca46.Coremail.00107082@163.com> <20230201180115.GB2626@voyager> <20230209190316.GU4163@brightrain.aerifal.cx> <23cd3146-4e39-6549-24ae-7fe7f24bed08@ispras.ru> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <23cd3146-4e39-6549-24ae-7fe7f24bed08@ispras.ru> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] Re:Re: [musl] 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