Why this inversion count merge sort algorithm is giving wrong answer

Question

Here is code I have written for inversion count in c++. If you write some other recursion method. Please try to explain it to me. I am storing inversion count in countI. I am getting 2 as output for array A[] i have declared in main function.

 #include<iostream>
 #include<math.h>


    using namespace std;
    int countI = 0;
    void merge(int A[], int p, int q, int r)
    {
        int n1 = q - p + 1;
        int n2 = r - q;
        int *L;
        L = new int[n1];
        int *R;
        R = new int[n2];
        for (int i = 1; i <= n1; i++)
        {
            L[i] = A[p + i - 1];
            //  cout << A[p + i - 1]<<endl;
            //cout << L[i];
        }
        for (int j = 1; j <= n2; j++)
            R[j] = A[q + j];
        int i = 1, j = 1;

        //  cout << "li " << L[n1]<<"\t"<<R[n2];

        for (int k = p; k <= r; k++)
        {

            if ((L[i] <= R[j] && i <= n1) || j>n2)
            {
                A[k] = L[i];
                //cout << A[k];
                i++;

            }
            else
            {
                A[k] = R[j];
                j++;
                if (i<n1)
                countI += n1 - i+1; //here I am counting the inversion.
                //cout <<endl<<"R"<< R[j];
            }
        }
    }
    void mergeSort(int A[], int p, int r)
    {
        if (p < r)
        {
            //      cout << A[8];
            int sum = p + r;
            //int q = (sum) / 2 + (sum % 2);
            int q = (sum) / 2;
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            merge(A, p, q, r);

        }
    }



    int main()
    {
        //I am considering array from index 1
        int A[] = { 0, 1, 3, 5,2,4,6 };
    //  int arr[100001];
        int i = 1;
        int n = 0;
        //while (scanf("%d", &n) != EOF) { arr[i++] = n; }

        mergeSort(A, 1, 6);
        for (int i = 1; i <= 6; i++)
        {
            cout << A[i] << " ";
        }
        cout << "\n " << countI;
        system("pause");
        return 0;
    }

Answer 1

You should note C++ uses 0 index based arrays. The first element of L and R are 0, not 1. The same thing when you call mergeSort in you main. try mergeSort(A, 0, 5)

While your consistent with your mistake of indexing starting at 1. You run off the end of your arrays by 1. This can cause your program to crash; however, when it doesn't you often get weird answers (which are hard to debug) because you're improperly accessing and writing over memory.

Here is some pseudo code (for 0 indexed based arrays) that will count inversions while performing merge sort.

merge(A, p, m , q){
  B = [] // array size of q - p + 1
  i = p, j = m+1, k = 0, inv = 0
  while (i <= m && j <= q){
    if (A[i] < A[j])
      B[k++] = A[i++]
    else{
      B[k++] = A[j++]
      inv += m - i + 1
    }
  }
  while (i <= m)     // copy rest of left side to temp array
    B[k++] = A[i++]  // otherwise it may be overwritten
  i = 0;
  while (i < k){     // copy temp array elements back to A
    A[p+i] = B[i]
    ++i
  }
  return inv
}

merge_sort(A, p, q){
  if (p == q)
    return 0;
  m = floor((p + q)/2)
  inv1 = merge_sort(A, p, m)
  inv2 = merge_sort(A, m+1, q)
  return inv1 + inv2 + merge(A, p, m, q)
}

// you can call it like this:
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  // 10 Elements
inversions = merge_sort(A, 0, 9)    // sort and count inversions from index 0 to index 9