viewing paste topic/4321- haru_key_merge-sort | Athena

Posted on the
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
prontera,152,188,5  script  merge sort keyworld 100,{
    .@total = 1000; 
    freeloop 1;
    for ( .@i = 0; .@i < .@total; .@i++ )
        .@array[.@i] = rand(1000);
    .@start = gettimetick(0);
    callfunc "merge_sort_keyworld", .@array, .@output, .@total;
    .@end = gettimetick(0);
    for ( .@i = 0; .@i < .@total; .@i++ )
        dispbottom .@array[ .@output[.@i] ] +"";
    dispbottom "time used -> "+( .@end - .@start )+" mili-seconds"; // 405-422
    end;
}
 
prontera,155,188,5  script  merge sort haru 100,{
    .@total = 1000; 
    freeloop 1;
    for ( .@i = 0; .@i < .@total; .@i++ )
        .@array[.@i] = rand(1000);
    .@start = gettimetick(0);
    callfunc "merge_sort_haru", .@array, .@output, .@total;
    .@end = gettimetick(0);
    for ( .@i = 0; .@i < .@total; .@i++ )
        dispbottom .@array[ .@output[.@i] ] +"";
    dispbottom "time used -> "+( .@end - .@start )+" mili-seconds"; // 452-468
    end;
}
 
//  callfunc "merge_sort", <input array>, <output index>, <total index>;
// Credits to Haru -> http://hercules.ws/board/topic/4321-
function    script  merge_sort_haru {
    .@size = getarg(2);
    copyarray .@arr, getarg(0), .@size;
    while ( .@i < .@size ) {
        set getelementofarray(getarg(1), .@i), .@i;
        .@i++;
    }
    .@width = 1;
    while ( .@width < .@size ) {
        .@i = 0;
        while ( .@i < .@size ) {
            .@left = .@i;
            .@middle = .@i + .@width;
            .@right = .@i + 2*.@width;
            if (.@size < .@middle) .@middle = .@size;
            if (.@size < .@right) .@right = .@size;
            .@i0 = .@left;
            .@i1 = .@middle;
            .@j = .@left;
            while ( .@j < .@right ) {
                if (.@i0 < .@middle && (.@i1 >= .@right || .@arr[.@i0] <= .@arr[.@i1])) {
                    .@tmp_array[.@j] = .@arr[.@i0];
                    .@tmp_array2[.@j] = getelementofarray(getarg(1), .@i0);
                    .@i0++;
                } else {
                    .@tmp_array[.@j] = .@arr[.@i1];
                    .@tmp_array2[.@j] = getelementofarray(getarg(1), .@i1);
                    .@i1++;
                }
                .@j++;
            }
            .@i += 2 * .@width;
        }
        .@width *= 2;
        copyarray .@arr, .@tmp_array, .@size;
        copyarray getarg(1), .@tmp_array2, .@size;
    }
    return;
}
 
//  Keyworld's merge sort
function    script  merge_sort_keyworld {
    .@size = getarg(2);
    copyarray .@arr, getarg(0), .@size;
    while (.@i < .@size) {
        set .@idx[.@i], .@i;
        .@i++;
    }
    .@width = 1;
    while (.@width < .@size) {
        .@left = 0;
        while (.@left < .@size) {
            .@middle = .@size < .@left + .@width     ? .@size : .@left + .@width;
            .@right  = .@size < .@left + .@width * 2 ? .@size : .@left + .@width * 2;
            .@l      = .@left;
            .@m      = .@middle;
            while (.@l < .@middle && .@m < .@right) {
                if (.@arr[.@l] < .@arr[.@m]) {
                    .@tmp_arr[.@left] = .@arr[.@l];
                    .@tmp_idx[.@left] = .@idx[.@l];
                    .@l++;
                } else {
                    .@tmp_arr[.@left] = .@arr[.@m];
                    .@tmp_idx[.@left] = .@idx[.@m];
                    .@m++;
                }
                .@left++;
            }
            if (.@middle - .@l) {
                copyarray .@tmp_arr[.@left], .@arr[.@l], .@middle - .@l;
                copyarray .@tmp_idx[.@left], .@idx[.@l], .@middle - .@l;
                .@left += .@middle - .@l;
            }
            else if (.@right - .@m) { // I added 'else' but doesn't seem to improve the time
                copyarray .@tmp_arr[.@left], .@arr[.@m], .@right - .@m;
                copyarray .@tmp_idx[.@left], .@idx[.@m], .@right - .@m;
                .@left += .@right - .@m;
            }
        }
        .@width *= 2;
        copyarray .@arr, .@tmp_arr, .@size;
        copyarray .@idx, .@tmp_idx, .@size;
    }
    copyarray getarg(1), .@tmp_idx, .@size;
    return;
}
Viewed 1356 times, submitted by AnnieRuru.