Using MergeSort to count Inversions

• Feb 16th 2007, 02:26 PM
Richard Rahl
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 :)
• Feb 17th 2007, 03:18 PM
ThePerfectHacker
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.