Ticket #571: perf_sort.d

import tango.io.Console,
       tango.io.FileConduit,
       tango.io.MappedBuffer,
       tango.time.StopWatch,
       tango.core.Array,
       tango.stdc.stdio;


int main (char[][] args)
{
    char[][] dictionary;

    for (int i = 1; i < args.length; ++i)
    {
        char[] input;
        int inword;
        int wstart;

        auto mmap = new MappedBuffer(new FileConduit(args[i]));
        input = cast(char[]) mmap.slice;

        for (int j = 0; j < input.length; j++)
        {
            char c = input[j];

            if (c >= '0' && c <= '9')
            {
            }
            else if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
            {
                if (!inword)
                {
                    wstart = j;
                    inword = 1;
                }
            }
            else if (inword)
            {
                char[] word = input[wstart .. j];
                dictionary ~= word;
                inword = 0;
            }
        }
        if (inword)
        {
            char[] word = input[wstart .. input.length];
            dictionary ~= word;
        }
    }

    char[][] tmpA = dictionary.dup;
    char[][] tmpB = dictionary.dup;
    char[][] tmpC = dictionary.dup;
    StopWatch   w;
    double      a, b, c;

    w.start;
    sort( tmpA );
    a = w.stop;
    w.start;
    introSort( tmpB );
    b = w.stop;
    w.start;
    tmpC.sort;
    c = w.stop;
    printf( "Tango: %f\nintroSort: %f\nPhobos: %f\n", a, b, c );
    return 0;
}


alias char[] type;
enum : size_t { INSERTIONSORT_THRESHOLD = 80 }
bool cmp(type a, type b) {
    return a < b;
}
void swap(T)(inout T a, inout T b) {
    auto
    t = a;
    a = b;
    b = t;
}

void introSort(type[] a) {
    static type median(type a, type b, type c) {
        if (cmp(a, b))
            if (cmp(b, c))
                return b;
            else if (cmp(a, c))
                return c;
            else
                return a;
        else if (cmp(a, c))
            return a;
        else if (cmp(b, c))
            return c;
        else
            return b;
    }

    static void doIntroSort(type[] a, size_t maxDepth) {
        while (a.length > INSERTIONSORT_THRESHOLD) {
            if (maxDepth-- == 0)
                return heapSort(a);

            type pivot = median(a[0], a[$/2], a[$-1]);
            size_t cut = 0, i = a.length;

            do {
                while (cmp(a[cut], pivot))
                    ++cut;
                --i;
                while (cmp(pivot, a[i]))
                    --i;
                swap(a[cut++], a[i]);

            } while (cut < i);

            doIntroSort(a[cut..$], maxDepth);
            a = a[0..cut];
        }
    }

    if (a.length > 1) {
        size_t lg = 0;
        size_t i = a.length;
        do {
            ++lg;
            i /= 2;
        } while (i > 1);
        doIntroSort(a, lg*2);
        insertionSort(a);
    }
}


void insertionSort(type[] a) {
    for (size_t i = 1; i < a.length; ++i) {
        type val = a[i];

        size_t pos = i-1;
        for (; pos < a.length && cmp(val, a[pos]); --pos)
            a[pos+1] = a[pos];

        a[pos+1] = val;
    }
}


void heapSort(type[] a) {
    if (a.length <= 1)
        return;

    auto n = a.length;
    auto i = n / 2;

    for (;;) {
        type t = void;

        if (i > 0)
            t = a[--i];
        else {
            if (--n == 0)
                return;

            t = a[n];
            a[n] = a[0];
        }

        auto parent = i;
        auto child  = i*2 + 1;

        while (child < n) {
            if (child + 1 < n && cmp(a[child], a[child+1]))
                ++child;

            if (cmp(t, a[child])) {
                a[parent] = a[child];
                parent = child;
                child = parent*2 + 1;
            } else
                break;
        }

        a[parent] = t;
    }
}