Thread: Using MergeSort to count Inversions

Hey folks!

I'm trying to count inversions in a list using MergeSort. I've got MergeSort functioning properly, but can't figure out how and when to update the Inversion count in Merge. Here's my code:

Code:

int SortAndCount(int arr_list[], int leftSize, int rightSize)
{
        int invLeft=0, invRight=0, invBoth=0;

        if(leftSize < rightSize)
        {
                int middleValue = (leftSize+rightSize) / 2;
                invLeft = SortAndCount(arr_list, leftSize, middleValue);
                invRight = SortAndCount(arr_list, middleValue+1, rightSize);
                invBoth = MergeAndCount(arr_list, leftSize, rightSize);

        }
        return invLeft + invRight + invBoth;
}

int MergeAndCount(int arr_List[], int leftSize, int rightSize)
{
        int newSize = rightSize - leftSize + 1;
        int middleValue = (rightSize + leftSize) /2;
        int Inversions=0, totalInv=0;

        int *tempArray = new int[newSize];
        int posistion=0;
        int i, j, placement=0;

        for(i=leftSize; i<=middleValue; i++, posistion++)
        {
                tempArray[posistion]=arr_List[i];
        }
        for(i=rightSize; i >= middleValue+1; i--, posistion++)
        {
                tempArray[posistion]=arr_List[i];
        }
        for(i=0,j=newSize-1, placement=leftSize; i<=j; placement++)
        {
                if(tempArray[i]<=tempArray[j])
                {
                        arr_List[placement]=tempArray[i];

                        i++;

                } else {

                        Inversions = Inversions + ( i - j);
                        arr_List[placement] = tempArray[j];
                        j--;

                }

        }
        delete[] tempArray;
        return Inversions;
}

I know that Inversions must be incremented by the amount of items remaining in the first list, when the number in the second list is smaller then the second list, but I cannot get out the correct answer.

Any help is appreicated! Thanks

I do not know if this helps, but there is a another way to count inversions. Through Premutation Groups.
The degree of a premutation determines if an inversion is even or odd.