void merge_to( int *src1, int len1, int *src2, int len2, int *dst )
{
    while ( len1 || len2 )
    {
        if ( ( len1 && len2 && *src1 < *src2 ) || ( len1 && !len2 ) )
        {
            *dst++ = *src1++;
            -- len1;
        }
        else
        {
            *dst++ = *src2++;
            -- len2;
        }
    }
}

void sort_to( int *data, int *dst, int *scratch, int length, int *scratch_end )
{
    assert( length > 0 );

    if ( length == 1 )
    {
        *dst = *data;
        return;
    }

    int half = length / 2;
    int *new_scratch = scratch + ( length - half );

    assert( new_scratch <= scratch_end );

    sort_to( data + half, scratch, new_scratch, length - half, scratch_end );
    sort_to( data, data + ( length - half ), new_scratch, half, scratch_end );
    merge_to( data + ( length - half ), half, scratch, length - half, dst );
}

void sort( int *data, int length, int *scratch )
{
    if ( length < 2 )
        return;

    sort_to( data, data, scratch, length, scratch + 2 * length );
}