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