Re: std.partition is fucked

[Lutger]

fwiw, I found the code and attached it with a benchmark found in the bugreport 
(2966). It works only on arrays, might be buggy too. But it does sort ;)

Timings based on 1000_000 elements:

std.algorithm:  624 // modified with the fix posted in this thread
Builtin sort:  540
iterative introsort:  244



module introsort;
import std.functional;
import std.stdio;
import std.c.string;
import std.math;
import std.conv;
import std.perf;
import std.random;
import std.algorithm;

void main() {
    enum N = 1000_000;
    uint[] foo = new uint[N];

    foreach(ref elem; foo) {
        elem = uniform(0U, 4_000_000_000U);
    }

    auto bar = foo.dup;
    scope pc = new PerformanceCounter;
    pc.start;
    std.algorithm.sort(bar);
    pc.stop;
    writeln("std.algorithm:  ", pc.milliseconds);

    bar[] = foo[];
    pc.start;
    bar.sort;  // Builtin.
    pc.stop;
    writeln("Builtin sort:  ", pc.milliseconds);

    bar[] = foo[];
    pc.start;
    introsort(bar);
    pc.stop;
    writeln("iterative introsort:  ", pc.milliseconds);
}

/** assumes partion is located at array[$-1] */
size_t partition(T)(T[] array)
{
    size_t front = 0;
    foreach( i; 0 .. array.length - 1)
    {
        if(array[i] < array[$-1])               // if value < pivot
        {
            ptrSwap(&array[front], &array[i]);       // move value to the front
            front++;
        }
    }
    ptrSwap( &array[front], &array[$-1] );           // move pivot back to the front
    return front;                               // return new position of pivot
}

/** select pivot and move it to a[$-1 ]*/
void shiftPivot(T)(T[] a)
{
    size_t r = a.length - 1;
    size_t m = r / 2;

    if(a[0] < a[m])
    {
        if(a[m] < a[r])
            ptrSwap(&a[m], &a[r]);
        else
        {
            if (a[r] < a[0])
            {
                ptrSwap(&a[0], &a[r]);
            }
        }
    }
    else
    {
        if( a[0] < a[r] )
            ptrSwap(&a[0], &a[r]);
        else
            if (a[r] < a[m])
                ptrSwap(&a[m], &a[r]);
    }
}

unittest
{
    assert( [1,2,3].selectPivot() == 1 );
    assert( [1,3,2].selectPivot() == 2 );
    assert( [2,1,3].selectPivot() == 0 );
}

private enum QSORT_MIN_SIZE = 20;
private enum MAX_STACK_SIZE = 80;

T[] insertionSortInplace ( alias less = "a < b", T ) ( T[] array )
{
    alias binaryFun!(less) cmp;
    for ( int current = 1; current < array.length; ++current )
    {
        auto value = array[current];
        auto insertPos = current - 1;
        while ( insertPos >= 0 && !cmp( array[insertPos], array[current]) )
            insertPos--;
        array[insertPos + 1 .. current].move_to( array[insertPos + 2 .. current + 1] );
        array[insertPos + 1] = value;
    }
    return array;
}

auto introsort(T)(T[] collection)
{
     // determine max size of stack as function of collection size + constant
    size_t maxDepth = to!size_t( std.math.log2( collection.length ) + 10  );
    maxDepth = maxDepth > MAX_STACK_SIZE ? MAX_STACK_SIZE : maxDepth;
    size_t stackLength = ( maxDepth + 1 ) * 2 * size_t.sizeof;

    T[]* stack;
    stack = cast( T[]* )std.c.stdlib.alloca( stackLength );
    stack[0] = collection;

    size_t p = 0;
    size_t i = 1;

    while( i > 0 )
    {
        auto current = stack[--i];

        if(current.length < QSORT_MIN_SIZE)
        {
            insertionSortInplace(current);
        }
        else if( i >= maxDepth )
        {

            insertionSortInplace(current);
        }
        else
        {
            current.shiftPivot();

            p = 0;
            foreach( j; 0 .. current.length - 1)
            {
                if(current[j] < current[$-1])
                {
                    ptrSwap(&current[p], &current[j]);
                    p++;
                }
            }
            ptrSwap( &current[p], &current[$-1] );

            stack[i++] = current[0..p];
            stack[i++] = current[p+1..$];
        }
    }
    return collection;
}

auto move_to(T)(const T[] src, T[] dest)
in
{
    assert(src.length >= dest.length, "can't do that!");
}
body
{
    memmove(dest[].ptr, src.ptr, dest.length * T.sizeof);
    return dest;
}

void ptrSwap(T)(T a, T b)
{
    typeof(*T) tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}