Count merge inversions

Question

I am reading Algorithm Introduction, Second Edition. He has an exercise, problem 2.4

Let A [1 n] be an array of n different numbers. If I <j and A [i]> A [j], then the pair (i, j) is called the inversion of A.

e. Give an algorithm that determines the number of inversions in any permutation of n elements in the Θ (n lg n) worst case. (Hint: change the merge sort.)

Then I found this solution in the Instructor's Guide

COUNT-INVERSIONS ( A, p, r) inversions ← 0 if p < r then q ← ( p + r)/2 inversions ← inversions +C OUNT-I NVERSIONS ( A, p, q) inversions ← inversions +C OUNT-I NVERSIONS ( A, q + 1, r) inversions ← inversions +M ERGE -I NVERSIONS ( A, p, q, r) return inversions MERGE -INVERSIONS ( A, p, q, r) n1 ← q − p + 1 n2 ← r − q create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] for i ← 1 to n1 do L[i] ← A[ p + i − 1] for j ← 1 to n2 do R[ j ] ← A[q + j ] L[n 1 + 1] ← ∞ R[n 2 + 1] ← ∞ i ←1 j ←1 inversions ← 0 counted ← FALSE for k ← p to r do if counted = FALSE and R[ j ] < L[i] then inversions ← inversions +n1 − i + 1 counted ← TRUE if L[i] ≤ R[ j ] then A[k] ← L[i] i ←i +1 else A[k] ← R[ j ] j ← j +1 counted ← FALSE return inversions 

My question is: I found that the variable is considered really useless. In the first case, if can be set to TRUE , but this means that R [J] L [i], so in the last sentence it will be set to FALSE .

Can someone give me an example that could explain why counting is needed?

Answer 1

You're right, the counted variable counted useless, because it will always be false when testing it.

It seems that the author’s intention was to count the same element R[j] twice. But they did not notice that after counting R[j] , j will always increase due to the transition to the else clause, so there is no need for precaution.