MergSort won't sort the array-CodePudding

I wrote this code for sorting a array. It wouldn't sort any array and won't give an error either and I can't seem to find to root cause of this issue.

This code was written as a part of learning curve and Code is exactly the same from the YT video , I am learning from. I have google another code snippet and it works properly but I want to see here what the problem is so I can hopefully learn from it and void making the same problem in future

void merge(int arr[], int l, int mid, int r)
{
    int n1= mid-l 1;
    int n2= r-mid;

    int array1[n1];
    int array2[n2];

    for(int i=0; i<n1; i  )
    {
        array1[i]=arr[l i];
    }

    for(int i=0; i<n2; i  )
    {
        array2[i]=arr[mid 1 i];
    }

    int i=0; int j=0; int k=l;

    while(i<n1 && j<n2)
    {
        if(array1[i]<array2[j])
        {
            arr[k]=array1[i];
            i  ;k  ;
        }
        else
        {
            arr[k]=array2[j];
            j  ;k  ;
        }

        while(i<n1)
        {
            arr[k]=array1[i];
            i  ;k  ;
        }

        while(j<n2)
        {
            arr[k]=array2[j];
            j  ,k  ;
        }
    }
}

void mergeSort(int arr[], int l, int r)
{
    
    if (l<r)
    {
        int mid= (l r)/2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid 1, r);
        merge(arr, l, mid, r);
    }
   
}


int main()
{
    int arr[]={5,4,3,2,1};
    

    mergeSort(arr, 0, 4);
    for(int i=0; i<5; i  )
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

CodePudding user response：

I think you'll find that this loop

while(i<n1 && j<n2)
{
    if(array1[i]<array2[j])
    {
        arr[k]=array1[i];
        i  ;k  ;
    }
    else
    {
        arr[k]=array2[j];
        j  ;k  ;
    }

    while(i<n1)
    {
        arr[k]=array1[i];
        i  ;k  ;
    }

    while(j<n2)
    {
        arr[k]=array2[j];
        j  ,k  ;
    }
}

should be written as three separate loops like this

while(i<n1 && j<n2)
{
    if(array1[i]<array2[j])
    {
        arr[k]=array1[i];
        i  ;k  ;
    }
    else
    {
        arr[k]=array2[j];
        j  ;k  ;
    }
}

while(i<n1)
{
    arr[k]=array1[i];
    i  ;k  ;
}

while(j<n2)
{
    arr[k]=array2[j];
    j  ,k  ;
}

It helps to understand the merge sort algorithm itself. Only then can you write the code for it. Copying without understanding what you are copying doesn't teach you much.

Try executing the algorithm using pen and paper to get a better understanding of it.

I haven't tested the rest of your code there may still be bugs in it.

CodePudding user response：

 while(i<n1 && j<n2) ----> (2)
    {
        if(array1[i]<array2[j])
        {
            arr[k]=array1[i];
            i  ;k  ;
        }
        else
        {
            arr[k]=array2[j];
            j  ;k  ;
        }

        while(i<n1) -----> (1) this part is not running when required 
        {
            arr[k]=array1[i];
            i  ;k  ;
        }

        while(j<n2) -----> (1) this part is not running when required 
        {
            arr[k]=array2[j];
            j  ,k  ;
        }
    }

as it is wrapped inside (2)

while(i<n1 && j<n2)

(1) should be out of block of (2), as it needs to add all the items that were not added to the array as i or j becomes greater than n1 or n2, falsifying the condition i<n1 && j<n2