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", , , ; // 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; }