Results 1 to 2 of 2

Math Help - Using MergeSort to count Inversions

  1. #1
    Feb 2007

    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:

    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++)
            for(i=rightSize; i >= middleValue+1; i--, posistion++)
            for(i=0,j=newSize-1, placement=leftSize; i<=j; placement++)
                    } else {
                            Inversions = Inversions + ( i - j);
                            arr_List[placement] = tempArray[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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Nov 2005
    New York City
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of inversions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 14th 2010, 01:04 PM
  2. Inversions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 31st 2010, 03:12 PM
  3. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 11th 2010, 03:12 PM
  4. Another IRV question... Inversions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 25th 2009, 04:49 PM
  5. Inversions of a permutation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2008, 02:22 PM

Search Tags

/mathhelpforum @mathhelpforum