Help in Merge Sort

general
,
1

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;
    }
2

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!

3

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…

4

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
5

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

6

@rinem had already pointed out the error! :slight_smile: