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;
}