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
I think you're right. The solution author is an experienced algorithmist, but with an entire book of exercises to solve, it's sort of inevitable that some of the answers won't be perfect.
Why don't you write to the authors?