In Corman, Introduction To Algorithms, 3rd edition, question 2-4 it asks to count the number of inversions in a list of numbers in $\theta( n \lg n )$ time. He uses a modified Merge Sort to accomplish this. However, there is something in his algorithm which seems redundant / unnecessary to me:
MERGE-INVERSIONS(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q + j]
L[n1 + 1] = infinity
R[n2 + 1] = infinity
i = 1
j = 1
inversions = 0
counted = FALSE
for k = p to r
if counted == FALSE and R[j] < L[i]
inversions = inversions + n1 - i + 1
counted = TRUE
if L[i] <= R[j]
A[k] = L[i]
i++
else A[k] = R[j]
j++
counted = FALSE
return inversions
The counted
variable seems redundant to me and I would have written the last for loop as follows:
inversions = 0
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i++
else A[k] = R[j]
inversions = inversions + n1 - i + 1
j++
return inversions
What am I missing, or is counted
really unnecessary?