function	script	test_sort	{
	freeloop true;
	.@total = 1000;
	for ( .@i = 0; .@i < .@total; .@i++ )
		.@array[.@i] = rand(50);
	.@start = gettimetick(0);
	callfunc getarg(0), .@array, .@output, .@total;
	.@end = gettimetick(0);
	for ( .@i = 0; .@i < .@total; .@i++ )
		.@print$[.@i] = .@array[ .@output[.@i] ];
	debugmes implode( .@print$, "," );
	dispbottom "time used -> "+( .@end - .@start )+" mili-seconds";
	
}

prontera,152,188,5	script	test merge sort haru	1_F_MARIA,{
	callfunc "test_sort", "merge_sort_haru";
	end;
}

prontera,155,188,5	script	test merge sort keyworld	1_F_MARIA,{
	callfunc "test_sort", "merge_sort_index";
	end;
}

prontera,158,188,5	script	test counting sort	1_F_MARIA,{
	callfunc "test_sort", "counting_sort_index";
	end;
}

prontera,161,188,5	script	test comb sort keyworld	1_F_MARIA,{
	callfunc "test_sort", "comb_sort_index";
	end;
}

prontera,164,188,5	script	test comb sort haru	1_F_MARIA,{
	callfunc "test_sort", "comb_sort_haru";
	end;
}

prontera,158,185,5	script	counting sort asm	1_F_MARIA,{
	callfunc "test_sort", "counting_sort_index_asm";
	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_index	{
	//.@state = freeloop();
	.@size  = getarg(2, getarraysize(getarg(0)) );

	//freeloop(1);
	copyarray .@_arr, getarg(0), .@size;

	while ((++.@i) < .@size) { // start at index 1
		.@_idx[.@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;
			}

			if (.@right - .@m) {
				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), .@_idx, .@size;
	//freeloop(.@state);

	return;
}

//	my counting sort, idea from keyworld
function	script	counting_sort_index	{
	.@total = .@size = getarg( 2, getarraysize( getarg(0) ) );
	copyarray .@arr, getarg(0), .@size;
	while ( .@i < .@size ) {
		setd ".@index_"+ .@arr[.@i] +"["+( .@tmp[.@arr[.@i]] )+"]", .@i;
		.@tmp[.@arr[.@i]]++;
		.@i++;
	}
	do {
		.@index = getarraysize(.@tmp) -1;
		.@tmp[.@index]--;
		.@out[.@size-1] = getd( ".@index_"+ .@index +"["+( .@tmp[.@index] )+"]" );
		.@size--;
	} while( .@size );
	copyarray getarg(1), .@out, .@total;
	return;
}


/** Made by Keyworld
 * Sorting array using a Comb Sort algorythm
 * export a sorted list of the array index
 * http://en.wikipedia.org/wiki/Comb_sort
 *
 * @param {array} input
 * @param {array} sorted input's input
 * @param {optional|integer} array size
 */
function	script	comb_sort_index	{
	//.@state = freeloop();
	.@size = getarg(2, getarraysize(getarg(0)) );
	.@gap  = .@size;

	//freeloop(1);
	copyarray .@_arr, getarg(0), .@size;

	while ((++.@i) < .@size) { // start at index 1
		.@_idx[.@i] = .@i;
	}

	do {
		.@gap  = .@gap > 1 ? .@gap * 10 / 13 : .@gap;
		.@i    = .@gap;
		.@swap = -1;

		while (.@i < .@size) {
			if (.@_arr[.@i-.@gap] > .@_arr[.@i]) {
				.@swap         = .@i - .@gap;

				.@tmp          = .@_arr[.@swap];
				.@_arr[.@swap] = .@_arr[.@i];
				.@_arr[.@i]    = .@tmp;

				.@tmp          = .@_idx[.@swap];
				.@_idx[.@swap] = .@_idx[.@i];
				.@_idx[.@i]    = .@tmp;
			}
			.@i++;
		}
	} while (.@swap > -1 || .@gap > 1);

	copyarray getarg(1), .@_idx, .@size;
	//freeloop(.@state);
	return;
}

//	callfunc "comb_sort", <input array>, <output index>, <total index>;
function	script	comb_sort_haru	{
	.@size = .@gap = getarg(2);
	copyarray .@arr, getarg(0), .@size;
	while ( .@i < .@size ) {
		set getelementofarray( getarg(1), .@i ), .@i;
		.@i++;
	}
	.@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;
				.@tmp = getelementofarray( getarg(1), .@i );
				set getelementofarray( getarg(1), .@i ), getelementofarray( getarg(1), .@i + .@gap );
				set getelementofarray( getarg(1), .@i + .@gap ), .@tmp;
				.@swap = 1;
			}
			.@i++;
		}
	} while ( .@swap || .@gap10 > 10 );
	return;
}

//	my counting sort, idea from keyworld
function	script	counting_sort_index_asm	{
	.@total = .@size = getarg( 2, getarraysize( getarg(0) ) );
	copyarray .@arr, getarg(0), .@size;
	LOOP1:
		setd ".@index_"+ .@arr[.@i] +"["+( .@tmp[.@arr[.@i]] )+"]", .@i;
		.@tmp[.@arr[.@i]]++;
		.@i++;
		__jump_zero ( .@i == .@size ), LOOP1;
	LOOP2:
		.@index = getarraysize(.@tmp) -1;
		.@tmp[.@index]--;
		.@out[.@size-1] = getd( ".@index_"+ .@index +"["+( .@tmp[.@index] )+"]" );
		.@size--;
		__jump_zero !.@size, LOOP2;
	copyarray getarg(1), .@out, .@total;
	return;
}