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 17291 invoked from network); 9 Feb 2023 20:18:30 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 9 Feb 2023 20:18:30 -0000 Received: (qmail 32474 invoked by uid 550); 9 Feb 2023 20:18:27 -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 32442 invoked from network); 9 Feb 2023 20:18:26 -0000 Date: Thu, 9 Feb 2023 15:18:14 -0500 From: Rich Felker To: Alexander Monakov Cc: musl@lists.openwall.com, Markus Wichmann Message-ID: <20230209201814.GW4163@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> <20230209195245.GV4163@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230209195245.GV4163@brightrain.aerifal.cx> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] Re:Re: [musl] 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