Hi all,

As I mentioned a while back on IRC, I've been looking into wikisort[1]
and grailsort[2] to see if either of them would be a good candidate for
use as musl's qsort.

The C-language reference implementations of both of these algorithms are
inappropriate, as they're both very large, not type-agnostic, and are
not written in idiomatic C.  Some of the complexity of both comes from
the fact that they are stable sorts, which qsort is not required to be.

Attached is an implementation of qsort based on a predecessor of the
paper that grailsort is based on, which describes an unstable block
merge sort.  The paper is available at [3].  My algorithm deviates a
little bit from what the paper describes, but it should be pretty easy
to follow.

You can find my test program with this algorithm and others at [4].
Some of the implementations included are quicksort variants, so the
"qsort-killer" testcase will trigger quadratic behavior in them.  If you
want to run this you should consider reducing the maximum input size in
testcases.h, disabling the qsort-killer input at the bottom of
testcases.c, or disabling the affected sort algorithms ("freebsd",
"glibc quicksort", and depending on your libc, "system") in sorters.c.

Here are the numbers comparing musl's current smoothsort with the
attached grailsort code for various input patterns and sizes.  The test
was run on x86_64, compiled with gcc 4.8.3 at -Os:

                              random              sorted             reverse            constant        sorted+noise       reverse+noise        qsort-killer    elements
                     compares     ms     compares     ms     compares     ms     compares     ms     compares     ms     compares     ms     compares     ms
musl smoothsort        327818     11        19976      0       268152      8        19976      0       142608      5       289637      8       139090      4       10000
                      4352267     97       199971      2      3327332     59       199971      2      2479200     45      3826143     68      1803634     37      100000
                     54441776    945      1999963     29     40048748    663      1999963     27     32506944    577     47405848    798     21830972    411     1000000
                    652805234  12300     19999960    289    465600753   7505     19999960    293    402201458   6891    572755136   9484    259691645   4741    10000000

grailsort              161696      2        71024      0        41110      0        28004      0       143195      1       125943      1        89027      0       10000
                      1993908     27       753996      2       412840      5       270727      3      1818802     15      1640569     17      1064759     10      100000
                     23428984    330      7686249     27      4177007     74      2729965     41     21581351    192     19909192    211     12325132    119     1000000
                    266520949   3884     75927601    277     42751315    901     28243939    436    248048604   2343    232357446   2575    139177031   1368    10000000

As far as code size, here are before and after sizes as reported by
size(1) for bsearch.o, qsort.o, and a minimal statically linked program
using qsort:

                before      after
    bsearch.o      116        160
    qsort.o       1550       1242
    statictest    2950       2819

At -O2, the before and after sizes show the same basic pattern.  At -O3,
gcc performs more aggressive inlining on the grailsort code, and it
balloons to more than twice the size of musl's current code.

For the sake of soft-float targets, I'd also like to look at replacing
the call to sqrt with an integer approximation.  But before I go much
further, I'd like to post the code here and get some feedback.

1. https://github.com/BonzaiThePenguin/WikiSort
2. https://github.com/Mrrl/GrailSort
3. http://akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/Huang88.pdf
4. http://git.koorogi.info/cgit/qsort_compare/

--
Bobby Bingham