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=-0.8 required=5.0 tests=DKIM_ADSP_CUSTOM_MED, DKIM_INVALID,DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI, RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 18534 invoked from network); 9 Feb 2023 20:27:44 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 9 Feb 2023 20:27:44 -0000 Received: (qmail 5893 invoked by uid 550); 9 Feb 2023 20:27:41 -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 5861 invoked from network); 9 Feb 2023 20:27:40 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=JEGS1rLgMZKkts6uK3QOjFZiqq/6Eqpi+dKlC0E/3Xw=; b=SSoAmJFLz3undljjziW9ErNsL5pZsGmFsrHVUzE/pVwAnF5qLp8Gu5k2nCFxym7XwR HvdaxYb4xOW+3XfuZ/EB4Nlmtvr9zPITsI/JrJATdkjxl8TEaywZD7F88ATGSH1Fjoej ACwqUteJjk6laz54Z8msa90eePJJf6cSCgRv3nekMwuXCRwPEH01jn+3IIfq1FK9grFl +MkDDkAvCHoipN8FoZiOoNniTl3fS16KfB4rzY85d0wq+E4festFXiI7u4k11gsvYWx1 8DijAst4smqq5jg60lE/T9EXCP4tHva2nXu63aF1b6r7hnirwuuqPEEVZl8Ckm3tW3rc KDKQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=JEGS1rLgMZKkts6uK3QOjFZiqq/6Eqpi+dKlC0E/3Xw=; b=vYmcI1rL/dBqKyDBwMSQj74S/oaTeKofGiVto2bq7AM316dP6LPneGuimm9kZ0RRaG l6XRaGypYQhLi5kFlRcKwTwq4E19XF7eosZboQk9kxkYVXL/8vdjqTjii3IHjGKT1lIf OUt44qoBDYlpEtARInJkLvbVdVzSTkiFAjqbzFJ5d1TTt/rBQNKHx6ALmycNnbeuy4Uv 2GtbLjEdqNLkRnrJjVpB0p3+I+odv6lffYWTcjmnHsyPysz3e9ciN57QPKz+bXqjfhKR 2LTX2JVE9HNkfjsY4KGtQ0giI6/feNexvO5dmv0jK+0ngyfSOTmVS0KJ+qLKwExNGGjc irzw== X-Gm-Message-State: AO0yUKVQFHdsLj0aG+yxgMIQndSrVYiflGlF936iq4lMxr4E5UYjIaCO /rGePW1b1So8kev5RBxXSNQ16YicXHSMddy4EThX7ba408U= X-Google-Smtp-Source: AK7set9ThUYszAF2ubjHjQV8mAYSAWxpF9nE8A3CoEC03hxA2kGyyteT8qYTKjUGC4VcYQCFawUMjGm4rIi7fVC1Gtg= X-Received: by 2002:a81:a207:0:b0:3d4:9cd5:353c with SMTP id w7-20020a81a207000000b003d49cd5353cmr1142216ywg.394.1675974448616; Thu, 09 Feb 2023 12:27:28 -0800 (PST) MIME-Version: 1.0 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> <20230209201814.GW4163@brightrain.aerifal.cx> In-Reply-To: <20230209201814.GW4163@brightrain.aerifal.cx> From: Pierpaolo Bernardi Date: Thu, 9 Feb 2023 21:27:17 +0100 Message-ID: To: musl@lists.openwall.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: Re: [musl] Re:Re: [musl] qsort On Thu, Feb 9, 2023 at 9:18 PM Rich Felker wrote: > > 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..? I too knew that glibc used to use introsort. I had examined the code. BUT that was many years ago, and my memory must be failing. Wikipedia says: "Introsort or some variant is used in a number of standard library sort functions, including some C++ sort implementations. The June 2000 SGI C++ Standard Template Library stl_algo.h implementation of unstable sort uses the Musser introsort approach with the recursion depth to switch to heapsort passed as a parameter, median-of-3 pivot selection and the Knuth final insertion sort pass for partitions smaller than 16. The GNU Standard C++ library is similar: uses introsort with a maximum depth of 2=C3=97log2 n, followed by an insertion sort on partitions smaller than 16.[3] LLVM libc++ also uses introsort with a maximum depth of 2=C3=97log2 n, however the size limit for insertion sort is different for different data types (30 if swaps are trivial, 6 otherwise). Also, arrays with sizes up to 5 are handled separately.[4] Kutenin (2022) provides an overview for some changes made by LLVM, with a focus on the 2022 fix for quadraticness.[5] The Microsoft .NET Framework Class Library, starting from version 4.5 (2012), uses introsort instead of simple quicksort.[6] Go uses introsort with small modification: for slices of 12 or less elements it uses Shellsort instead of insertion sort, and more advanced median of three medians of three pivot selection for quicksort. Java, starting from version 14 (2020), uses a hybrid sorting algorithm that uses merge sort for highly structured arrays (arrays that are composed of a small number of sorted subarrays) and introsort otherwise to sort arrays of ints, longs, floats and doubles." Cheers