mailing list of musl libc
 help / color / mirror / code / Atom feed
From: Pierpaolo Bernardi <olopierpa@gmail.com>
To: musl@lists.openwall.com
Subject: Re: [musl] Re:Re: [musl] qsort
Date: Thu, 9 Feb 2023 21:27:17 +0100	[thread overview]
Message-ID: <CANY8u7Haye=LeNw9r1CHseKo2sBPJHsF3OCp3Z=X3vGhxRavUA@mail.gmail.com> (raw)
In-Reply-To: <20230209201814.GW4163@brightrain.aerifal.cx>

On Thu, Feb 9, 2023 at 9:18 PM Rich Felker <dalias@libc.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

  reply	other threads:[~2023-02-09 20:27 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-01-20  1:49 Guy
2023-01-20 12:55 ` alice
2023-01-30 10:04   ` [musl] " David Wang
2023-02-01 18:01     ` Markus Wichmann
2023-02-02  2:12       ` [musl] " David Wang
2023-02-03  5:22         ` [musl] " David Wang
2023-02-03  8:03           ` Alexander Monakov
2023-02-03  9:01             ` [musl] " David Wang
2023-02-09 19:03       ` Rich Felker
2023-02-09 19:20         ` Alexander Monakov
2023-02-09 19:52           ` Rich Felker
2023-02-09 20:18             ` Rich Felker
2023-02-09 20:27               ` Pierpaolo Bernardi [this message]
2023-02-10  4:10             ` Markus Wichmann
2023-02-10 10:00         ` [musl] " David Wang
2023-02-10 13:10           ` Rich Felker
2023-02-10 13:45             ` [musl] " David Wang
2023-02-10 14:19               ` Rich Felker
2023-02-11  5:12                 ` [musl] " David Wang
2023-02-11  5:44                   ` alice
2023-02-11  8:39                     ` Joakim Sindholt
2023-02-11  9:06                       ` alice
2023-02-11  9:31                         ` [musl] " David Wang
2023-02-11 13:35                         ` Rich Felker
2023-02-11 17:18                           ` David Wang
2023-02-16 15:15       ` David Wang
2023-02-16 16:07         ` Rich Felker
2023-02-17  1:35           ` [musl] " David Wang
2023-02-17 13:17           ` Alexander Monakov
2023-02-17 15:07             ` Rich Felker
2023-02-11  9:22     ` [musl] " Markus Wichmann
2023-02-11  9:36       ` [musl] " David Wang
2023-02-11  9:51       ` David Wang
2023-01-20 13:32 ` [musl] qsort Valery Ushakov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CANY8u7Haye=LeNw9r1CHseKo2sBPJHsF3OCp3Z=X3vGhxRavUA@mail.gmail.com' \
    --to=olopierpa@gmail.com \
    --cc=musl@lists.openwall.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).