[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
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.
