algorithmmergesortclrsinversion

Modifying merge sort to count the number of inversions


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:

The MergeSort recursive function

The Merge function

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

Solution

  • 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?