Please read this before you rush to mark this as duplicate! - This is not about the actual modification, this is about checking if a particular inversion has been counted or not.
So there is this question in the popular CLRS' Introduction to Algorithms book that asks you to modify merge sort to calculate the number of inversions in an array. The authors also generously provide solution to this problem 2-4 here, whose screenshots I have attached below:
My question: In the second screenshot, the author has used a boolean counted = FALSE to check if the inversions corresponding to a particular R[j] for some value of j have been already counted or not. I am quite confused because of this as I think it is redundant.
We count inversions here:
if counted == FALSE and R[j] < L[i]
inversions = inversions + n1 - i + 1
counted = TRUE
so counted becomes TRUE only when R[j] < L[i], which is ALSO the else part below:
...
else
A[k] = R[j]
j = j + 1
counted = FALSE
So whenever we have R[j] < L[i] we copy R[j] into A[k] and increase the value of j by 1, which makes sure that we never encounter the previous R[j] again in the loop. In my opinion this makes the counted boolean redundant.
Or is there something more to it? Is there any particular example that breaks if we remove the counted boolean:
// my suggestion
...
for k = p to r
if R[j] < L[i]
inversions = inversions + n1 - i + 1
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1

