Count inversions with merge-sort

I am reading "Introduction of Algorithm, 2nd edition". It has an exercise, Problem 2.4

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

d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(n lg n) worst-case time. (Hint: Modify merge sort.)

Then I found this solution in the Ins开发者_Python百科tructor's Manual

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 the variable counted really useless. In the first if clause, it might be set to TRUE, but that means R[J] < L[i], so in the last else clause, it's going to be set back to FALSE.

Could anyone give me an example that could explain why counted is needed?

You're right, the counted variable is useless, since it will always be false when it's tested.

It looks like the author's intention was to avoid counting the same R[j] element twice. But they didn't notice that after counting R[j], j will always be incremented due to going into the else clause, so there's no need for the precaution.