I've got a homework from school to create a project that would count inversions in an array of integers. I first tried to bruteforce it, but as I expected, I didn't pass the time limit. So after some googling and trying to fully understand mergeSort and how to implement counting of inversions into it, I've made up this code, which unfortunately outputs wrong count, whilst sorting the array correctly:
procedure mergeSort(var arr, pomarr : array of longint; start, stop :
longint; var inv : longint);
var
mid,i,j,k : longint;
begin
mid := (start + stop) div 2;
if (start < mid) then mergeSort(arr,pomarr,start,mid,inv);
if (mid+1 < stop) then mergeSort(arr,pomarr,mid+1,stop,inv);
i := start;
k := start;
while (i<= mid) and (j <= stop) do begin
if (arr[i] < arr[j]) then begin
pomarr[k] := arr[i];
i += 1;
end
else begin
pomarr[k] := arr[j];
inv += mid - i;
j += 1;
end;
k += 1;
end;
while (i <= mid) do begin
pomarr[k] := arr[i];
i += 1;
k += 1;
end;
while (j <= stop) do begin
pomarr[k] := arr[j];
j += 1;
k += 1;
end;
for k := start to stop do begin
arr[k] := pomarr[k];
end;
end;
Thanks in advance for all your help. I know it's just some stupid mistake in a declaration, but I just can't seem to find it.
So I somewhat managed to fix my problem. I asked my teacher what might cause this issue, and he told me, that there is actually a difference between declaring a type of variable in the head of the program and declaring it in the body. Afterwards I fixed my program by creating an array type:
type
numlist = array[1..250000] of longint;
and declared my used arrays in function and everywhere else via this type. And it actually worked.
From what I could collect, if you declare an array without using the type, iteration actually starts from 0, not from 1 as usual. I honestly have no idea how these two facts are related, but it fixed my problem and now it runs as intended.
If anybody knows what causes this iteration shift, please let me know. I'm actually even more confused than I was before.