// Arguments: (0): array length; (1): main (ids) array; (2): secondary (amounts) array
// Sorting is done in place, original array is not preserved.
function	script	bottomupmergesort_inplace	{
	.@size = getarg(0);
	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(1), .@i0) <= getelementofarray(getarg(1), .@i1))) {
					.@tmp_array[.@j] = getelementofarray(getarg(1), .@i0); // Swap main
					.@tmp_array2[.@j] = getelementofarray(getarg(1), .@i0); // Swap secondary
					++.@i0;
				} else {
					.@tmp_array[.@j] = getelementofarray(getarg(1), .@i1); // Swap main
					.@tmp_array2[.@j] = getelementofarray(getarg(1), .@i1); // Swap secondary
					++.@i1;
				}
			}
		}
		copyarray getarg(1), .@tmp_array, .@size;
		copyarray getarg(2), .@tmp_array2, .@size;
	}
	return;
}

// Arguments: (0): array length; (1): (ids) array; (2): Output (indices) array
// Original array is preserved. Only returns the sorted indices.
function	script	bottomupmergesort_idx	{
	.@size = getarg(0);
	copyarray .@arr, getarg(1), .@size;
	for (.@i = 0; .@i < .@size; ++.@i) {
		set getelementofarray(getarg(2), .@i), .@i);
	}
	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 || .@arr[.@i0] <= .@arr[.@i1])) {
					.@tmp_array[.@j] = .@arr[.@i0]; // Swap copy of main
					.@tmp_array2[.@j] = getelementofarray(getarg(2), .@i0); // Swap index
					++.@i0;
				} else {
					.@tmp_array[.@j] = .@arr[.@i1); // Swap copy of main
					.@tmp_array2[.@j] = getelementofarray(getarg(2), .@i1); // Swap index
					++.@i1;
				}
			}
		}
		copyarray .@arr, .@tmp_array, .@size;
		copyarray getarg(2), .@tmp_array2, .@size;
	}
	return;
}