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 596 times, submitted by AnnieRuru.