# Help in Merge Sort

I am trying to implement the Inversion Count problem for merge sort and have implemented it in c++ but I am not getting the desired output. Please help me find the bug in my program:

``````#include <iostream>

using namespace std;

void mergeArr(int a[], int l, int mid, int r)
{
int n1, n2;
int i,j,k;
int inv_count = 0;
n1 = mid - l + 1;
n2 = r - mid;
int temp[r-l+1];
int L[n1], R[n2];
for(i = 0;i < n1;i++)
L[i] = a[l+i];
for(j = 0;j < n2;j++)
R[j] = a[mid+j+1];
i = j = 0;
k = l;
while(i<n1 && j<n2)
{
if(L[i] <= R[j])
temp[k++] = L[i++];
else
{
temp[k++] = R[j++];
inv_count += (mid - i);
}
}
while(i<n1)
temp[k++] = L[i++];
while(j<n2)
temp[k++] = R[j++];
for(i=l;i<=r;i++)
a[i] = temp[i];
}
void mergeSort(int a[], int l, int r)
{
int inv_count = 0;
if(l < r)
{
int mid;
mid = (l + (r))/2;
mergeSort(a,l,mid);
mergeSort(a,mid+1,r);
mergeArr(a,l,mid, r);
}
//return inv_count;
}

int main()
{
cout<<"Enter the number of elements"<<endl;
int n;
cin>>n;
int a[n];
cout<<"Enter the elements: "<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<"Array before sorting: "<<endl;
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
mergeSort(a,0,n-1);
cout<<endl<<"Array after sorting: "<<endl;
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
//cout<<endl<<"Inversions: "<<mergeSort(a,0,n-1);
return 0;
}

int main()
{
cout<<"Enter the number of elements"<<endl;
int n;
cin>>n;
int a[n];
cout<<"Enter the elements: "<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<"Array before sorting: "<<endl;
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
/*mergeSort(a,0,n-1);
cout<<endl<<"Array after sorting: "<<endl;
for(int i=0;i<n;i++)
cout<<a[i]<<" ";*/
cout<<"Inversions: "<<mergeSort(a,0,n-1);
return 0;
}``````

hello!

You are updating the array ‘a’ at time of checking but notice one fact i always lies between l<= i <= mid so, when k becomes equal to i at some time then we have now updated the a[k] and next comparision is done with this updated a[i] and that is wrong!

Instead you can build a temporary array and store the result there first and at the end update the original array with the help of temporary!

Hope it helps!

One bug I could find in your program is that you are not adding the returned value of `inv_count` to the same variable in the mergeSort() function. Here’s the corrected code

``````void mergeSort(int a[], int l, int r)
{
int inv_count = 0;
if(l < r)
{
int mid;
mid = (l + (r))/2;
inv_count = mergeSort(a,l,mid);
inv_count += mergeSort(a,mid+1,r);
inv_count += mergeArr(a,l,mid+1, r);
}
return inv_count;
}``````
1 Like

You could compare your code with my code (which got accepted) to check for error if u want.
My solution: https://ide.geeksforgeeks.org/5N9xNnN6Eq

I did changes to my code as to told(check edited code), but now merge sort fails for the condition: 1 3 5 2 4 6 input of array…