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 + 1n2 = r - qlet L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arraysfor i = 1 to n1    L[i] = A[p + i - 1]for j = 1 to n2    R[j] = A[q + j] L[n1 + 1] = infinityR[n2 + 1] = infinityi = 1j = 1inversions = 0counted = FALSEfor 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 = FALSEreturn inversionsThe counted variable seems redundant to me and I would have written the last for loop as follows:inversions = 0for 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 inversionsWhat am I missing, or is counted really unnecessary?
Counting Inversions Using Merge Sort
algorithms;algorithm analysis;sorting;program correctness
We can show that after every iteration of the for-loop in question, counted is FALSE. Therefore, inversions = inversions + n1 - i + 1 is executed if and only if j++ is executed in the same iteration (both are guarded by R[j] < L[i]). Since neither i nor j is changed between evaluation of the two if conditions, this implies that your version is equivalent. We perform an induction over k. Before the loop, counted is explicitly set to FALSE. In any given iteration, we start (by induction hypothesis) with counted == FALSE. If L[i] <= R[j], counted is not changed throughout the current iteration. If the opposite is the case, counted is first set to TRUE, but reset to FALSE in the else block. For this, we note that the truth value of R[j] < L[i] remains unchanged from the first to the second if.I guess the extra block is there for didactic reasons.