function    script  mergesort   {
    .@left = getarg(0);
    .@right = getarg(1);
    if ( !getarg(5,0) ) {
        if ( .@right <= .@left )
            return -1;
        .@size = .@right - .@left +1;
        copyarray $@tmp_array, getarg(2), .@size;
    }
    if ( .@right > .@left ) {
        .@mid = ( .@left + .@right ) /2;
        callfunc "mergesort", .@left, .@mid, $@tmp_array, getarg(3), 0, 1;
        callfunc "mergesort", .@mid +1, .@right, $@tmp_array, getarg(3), 0, 1;
        callfunc "merge", .@left, .@mid +1, .@right, $@tmp_array, getarg(3);
    }
    return .@right - .@left +1;
}
 
function    script  merge   {
    .@left = getarg(0);
    .@mid = getarg(1);
    .@right = getarg(2);
    .@left_end = .@mid -1;
    .@pos = .@left;
    .@size = .@right - .@left +1;
    while ( .@left <= .@left_end && .@mid <= .@right ) {
        if ( getelementofarray( getarg(3), .@left ) <= getelementofarray( getarg(3), .@mid ) ) {
            set getelementofarray( getarg(4), .@pos ), getelementofarray( getarg(3), .@left );
            .@left++;
        }
        else {
            set getelementofarray( getarg(4), .@pos ), getelementofarray( getarg(3), .@mid );
            .@mid++;
        }
        .@pos++;
    }
    while ( .@left <= .@left_end ) {
        set getelementofarray( getarg(4), .@pos ), getelementofarray( getarg(3), .@left );
        .@left++;
        .@pos++;
    }
    while ( .@mid <= .@right ) {
        set getelementofarray( getarg(4), .@pos ), getelementofarray( getarg(3), .@mid );
        .@mid++;
        .@pos++;
    }
    while ( .@i < .@size ) {
        set getelementofarray( getarg(3), .@right ), getelementofarray( getarg(4), .@right );
        .@right--;
        .@i++;
    }
    return;
}
 
prontera,158,185,5  script  test merge sort 100,{
OnInit:
    sleep 1000;
    .@total = 1000;
    freeloop(1);
    for ( .@i = 0; .@i < .@total; ++.@i ) {
        .@array[.@i] = rand(10000);
    }
    .@time = gettimetick(0);
    callfunc "mergesort", 0, .@total -1, .@array, .@output;
    .@endtime = gettimetick(0);
    for ( .@i = 0; .@i < .@total; ++.@i )
        debugmes .@output[.@i];
    freeloop(0);
    debugmes "time used -> "+( .@endtime - .@time )+" milli-seconds";
    end;
}
 
function    script  bottomupmergesort   {
    .@size = getarg(0);
    copyarray getarg(2), getarg(1), .@size;
    for (.@width = 1; .@width < .@size; .@width *= 2) {
        // Combine sections of array a of width "width"
        for (.@i = 0; .@i < .@size; .@i += 2 * .@width) {
            .@left = .@i;
            .@middle = .@i + .@width;
            .@right = .@i + 2*.@width;
            if (.@size < .@middle) .@middle = .@size;
            if (.@size < .@right) .@right = .@size;
 
            .@i0 = .@left;
            .@i1 = .@middle;
            /* While there are elements in the left or right lists */
            for (.@j = .@left; .@j < .@right; ++.@j) {
                /* If left list head exists and is <= existing right list head */
                if (.@i0 < .@middle && (.@i1 >= .@right || getelementofarray(getarg(2), .@i0) <= getelementofarray(getarg(2), .@i1))) {
                    .@tmp_array[.@j] = getelementofarray(getarg(2), .@i0);
                    ++.@i0;
                } else {
                    .@tmp_array[.@j] = getelementofarray(getarg(2), .@i1);
                    ++.@i1;
                }
            }
        }
        copyarray getarg(2), .@tmp_array, .@size;
    }
    return;
}
 
prontera,158,185,5  script  test bu merge sort  100,{
OnInit:
    sleep 6000;
    .@total = 1000;
    freeloop(1);
    for ( .@i = 0; .@i < .@total; ++.@i ) {
        .@array[.@i] = rand(10000);
    }
    .@time = gettimetick(0);
    callfunc "bottomupmergesort", .@total, .@array, .@output;
    .@endtime = gettimetick(0);
    for ( .@i = 0; .@i < .@total; ++.@i )
        debugmes .@output[.@i];
    freeloop(0);
    debugmes "time used -> "+( .@endtime - .@time )+" milli-seconds";
    end;
}
 
//  ==================================================================================
 
//  callfunc "comb_sort", <input array>, <output index>, <total index>;
function    script  comb_sort   {
    .@size = getarg(2);
    copyarray .@arr, getarg(0), .@size;
    .@size = .@gap = getarg(2);
    .@gap10 = .@size * 10;
    do {
        if ( .@gap10 > 10 ) {
            .@gap10 = .@gap10 * 10 / 13;
            .@gap = .@gap10 / 10;
        }
        .@i = .@swap = 0;
        while ( .@i + .@gap < .@size ) {
            if ( .@arr[.@i] > .@arr[ .@i + .@gap ] ) {
                .@tmp = .@arr[.@i];
                .@arr[.@i] = .@arr[ .@i + .@gap ];
                .@arr[ .@i + .@gap ] = .@tmp;
                .@swap = 1;
            }
            .@i++;
        }
    } while ( .@swap || .@gap > 10 );
    copyarray getarg(1), .@arr, .@size;
    return;
}
 
prontera,155,185,6  script  test comb sort  100,{
OnInit:
    sleep 10000;
    .@total = 1000;
    freeloop(1);
    for ( .@i = 0; .@i < .@total; ++.@i ) {
        .@array[.@i] = rand(10000);
    }
    .@time = gettimetick(0);
    callfunc "comb_sort", .@array, .@output, .@total;
    .@endtime = gettimetick(0);
    for ( .@i = 0; .@i < .@total; ++.@i )
        debugmes .@output[.@i];
    freeloop(0);
    debugmes "time used -> "+( .@endtime - .@time )+" milli-seconds";
    end;
}