Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Wed, 13 Sep 2017 15:51:54 +0200
From: Markus Wichmann <>
Subject: Wrong info in libc comparison


there's a mistake on the libc comparison page Namely it states that glibc
uses introsort as sorting algorithm. It doesn't. Glibc uses a
bog-standard merge sort as main sorting algorithm. A major part of the
implementation is actually just devoted to optimized copying, and for
arrays of large objects it uses an interesting way to indirectly sort
them (i.e. it then allocates an array of references, sorts the
references, then uses a clever algorithm to get from sorted references
to a sorted array). But it's all just a standard merge sort.

However, merge sort on arrays requires a linear amount of scratch space,
so this merge sort has to allocate memory. Memory allocation is allowed
to fail, but sorting isn't, so, as a fallback, in case the allocation
fails (or would use more than half the physical memory, for some
reason), it falls back to quicksort. This quicksort is implemented with
a really funky scheme for an explicit stack (i.e., while I'd use

    while (stack_not_empty()) {
        if (subprob_worth_bothering_with()) {

they do something more like:

    while (stack_not_empty()) {
        if (subprob_worth_bothering_with()) {

), a median-of-three pivot selection, two-way partitioning (why couldn't
you be perfect for me?), and a minimum partition size of 4,
necessitating an insertion sort stage afterwards.

So, yeah, no introsort in sight. Introsort would be merge sort on large
arrays, then quicksort on smaller partitions, and finally insertion sort
for the smallest partitions.


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.