Where do I put the inversion counter in this merge sort algorithm?

Question

I am trying to count the number of inversions that occur during the merge sort progress of a 100,000 integer array. The values in the array are in no particular order. My question is simple, where in the merge sort algorithm would I apply the inversion counter? Below if the merge sort algorithm by itself, and the image after that is where I propose putting the inversion counter. The file reads correctly and the merge sort works correctly, I am only asking if my placement of the inversion counter is accurate. Any advice would be greatly appreciated!

I have edited the page to only include the merge function

 void merge(vector<int> &left, vector<int> &right, vector<int> &array, int &inversionCount) 
{
    int leftSize = left.size();
    int rightSize = right.size();
    int i = 0, l = 0, r = 0;

    while (l < leftSize && r < rightSize)
    {
        if (left[l] < right[r])
        {
            int temp1 = l;
            while ((right[r] > left[temp1]) && temp1 < left.size() - 1)
            {
                inversionCount++;
                temp1++;
            }
            array[i] = left[l];
            i++;
            l++;
        }
        else if (right[r] < left[l])
        {
            int temp1 = r;
            while ((left[l] > right[temp1]) && temp1 < right.size() - 1)
            {
                inversionCount++;
                temp1++;
            }
            array[i] = right[r];
            i++;
            r++;
        }
        else
        {
            array[i] = right[r];
            i++;
            r++;
        }
    }

    while (l < leftSize)
    {
        array[i] = left[l];
        i++;
        l++;
    }
    
    while (r < rightSize)
    {
        array[i] = right[r];
        i++;
        r++;
    }

}

Answer 1

From your comment, it sounds like you're on the right track.

However, let's look at a case of some random numbers, and skip the first few merges. We'll take the case of left[4,5,7,8,9] and right[1,2,3,5,6]. Perhaps some inversions have already been counted, but we'll just start here.

First, we check whether left[4] is greater than right[1]. It is, so we must increment our inversion counter. However, [4] is also greater than [2] and [3] in this case, and that must also be accounted for.

The question is, how can we do that? Well, when we realize than [4] is greater than [1], we can start another loop, inside the right array, incrementing our inversion counter until we encounter a value greater than or equal to 4, and at that point we stop. So in this case, we go +1 for [4] against [1], [2], and [3], and then we stop at right[5]. This leaves us with +3, and then we put down 4 in the new array, and start over with left[5], counting back up again.

Obviously we must save the index of right[1] before we begin this check, or else the MergeSort algorithm might get screwed up.

This is a naive approach though, since there is really no reason to count all the way back up when we look at left[5], since we know that left[5] > left[4], and we already know that left[4] was greater than several values in the right[] array. For something like 100,000 values, this naivety may cause your program to slow down quite a bit.