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