|
Message-ID: <CANY8u7Haye=LeNw9r1CHseKo2sBPJHsF3OCp3Z=X3vGhxRavUA@mail.gmail.com> Date: Thu, 9 Feb 2023 21:27:17 +0100 From: Pierpaolo Bernardi <olopierpa@...il.com> To: musl@...ts.openwall.com Subject: Re: Re:Re: qsort On Thu, Feb 9, 2023 at 9:18 PM Rich Felker <dalias@...c.org> 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×log2 n, followed by an insertion sort on partitions smaller than 16.[3] LLVM libc++ also uses introsort with a maximum depth of 2×log2 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
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.