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.1 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 10575 invoked from network); 10 Feb 2023 04:10:50 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 10 Feb 2023 04:10:50 -0000 Received: (qmail 21533 invoked by uid 550); 10 Feb 2023 04:10:47 -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 20472 invoked from network); 10 Feb 2023 04:10:46 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=gmx.net; s=s31663417; t=1676002235; bh=pZvqFNuoPDWUCMrAIZPiscRPDVxnYSyhHeDeuD3TJi4=; h=X-UI-Sender-Class:Date:From:To:Subject:References:In-Reply-To; b=hkzuGWIKtGgaBRch5PxjPcxYy5C6eHXtyxXEkzw3nP5ShzUGmo9Snfh2w01dPv4kC R9rbiD46T/y/g5M3xY1PwMDk/jYeYmh2G90YVrTrNV5Od/Sx8qUhz2fjlR5rYX5Y6i FV9C+sB7mPGWcf/6PySJ9yoh07g6OPC/JUfX+T7D+veri5+kO3DB9C4eILY641grvo iutPs8DgjBf1Gk4QQmJ/kOlG+cNvV7YdsYJf7s9WISlcoqPuCeH02iLdQjE5WWhPH4 uTEyFOxkakE0JUGETGKBGvA54dgJIakEvEBeXWVt56tAwUuh1Bper52OxLft/84vLY kXBDbYuzprQbA== X-UI-Sender-Class: 724b4f7f-cbec-4199-ad4e-598c01a50d3a Date: Fri, 10 Feb 2023 05:10:33 +0100 From: Markus Wichmann To: musl@lists.openwall.com Message-ID: <20230210041033.GA1903@voyager> 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.9.4 (2018-02-28) X-Provags-ID: V03:K1:k8MlLFKMVs+m6gq7dAoMOMLU+cRlANq/ZL1x2ZDDlz1EOjllgFd I+IMdB5zuMu7BxTnxC6qD/9qvGgtj5tn7b2PK9pJm6cV4o/UlzP3NU492zdbqINq4AO615q raCRIYMdakxNvFtE1RFJDQPbkmfKy5BBfd/G/RdTsa9nYzbkFzzY/z/3wvSnQajiHk/gXSK nassKqbGoS8oS6YEPyHiw== UI-OutboundReport: notjunk:1;M01:P0:FwY+k+miVlc=;/JPhb2wZdI6hayD99iA8t3Y/ofS j9HHjfLLRwIO7rCEpfXtp5xViH8McVOk4bTijBCbKPdvjHz7cSxh72QsSSBgWJyCp7Iy0hngQ 06LyP+J9uSwtG7to9o0IgOAEM6DtfEazX7BY6+vA6i1ycknWj4mU7sAyAsks0FwJ7GILSg7vw 8lxK+CCDqM9P/h42KZek/NDLHkyq+iscMN0fQ+mJCWoBMu3d/PAjz9oktIWyEAqfxuwt9Ab4T DIT3QxlxRIQb8mBY9MDIKy7KdH5gcZe6w0myoyzr4Vr3dxL2u6RQuVo0SzJte0l4afqHXQF8i ehBWSYMAWWuxkJoG0Rr5HgQuo60LRLUyvarFghhN9motkKU6gg2rbS2X6lu/ZhH8l330C2ovL ocrV75hlvm0F43jSsG2BR4wFWQUxvQZPheaXgWG6fB9xnXgwmWSbhwNFnDtGP2fG7VCj6oXp6 qu0TaBvKkAMSEHtbENzYeByIXAqw1d5WOuMpgB1ecO2Y4wTM8rLSjjHAWcoVHoM/xmbAlGjmK oL3pycNO13tTOOREmCHZGhC/qCQSVmse/oOeZ2fIPsGBV1Usz7lMlVhkkyCB6dTSWWpT1uHWj kyPM8hvDr9Ej164fuU4Yv4Yo7GXPBgE2mCFFCTLMXE/7qIUHfs9vpugEMwns9/Cmylf/BKYF6 TgNUyAJHemGwp/eH10DlslGh+PQOIo4IPYj3tW7xPJxbcXjSajxR0DqMnjIF5mkE/rGUVwdr2 uHBSOeyGlbYz0EDAHhS3du1Fa414SQ0O5F6rbhxRmz6XlDDBb7Q3OLWOEoL1Ryd3koj2WGJzV 7rHx1o8bMweD2S0RfIStmGaUDa6bjc5+OsCSlytP0pi0V6ZzqwReNwB76DNFTboB5ShB1QiO8 wmRXAldfdFgTSTe5h+HeYOZwsNKVhSdyXIsXDEtAxPUe/PQEqWySZ1376+UXPBaHoDykXWwp6 v9vv2g== Content-Transfer-Encoding: quoted-printable 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 introspect= s > > > 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 The latter. As I recall, I notified you about this because it was also wrong on the etalabs libc comparison page. Lemme check... yep, still wrong. Ciao, Markus