Wrong info in libc comparison

[Markus Wichmann <nullplan@gmx.net>]

Hello,

there's a mistake on the libc comparison page
http://www.etalabs.net/compare_libcs.html: 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

    push_total_problem();
    while (stack_not_empty()) {
        pop_subprob();
        if (subprob_worth_bothering_with()) {
            sort_partition();
            push_larger_subprob();
            push_smaller_subprob();
        }
    }

they do something more like:

    push_pseudo_problem();
    while (stack_not_empty()) {
        if (subprob_worth_bothering_with()) {
            sort_partition();
            figure_out_next_subproblem();
            then_maybe_push_or_pop_stuff();
        }
    }

), 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.

Ciao,
Markus