MergSort won't sort the array

Question

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

`int mid= (l+r)/2` -- This will have integer overflow if `l` and or `r` are large `int` values. For example, what if `l` is one less than the maximum integer? — PaulMcKenzie, Aug 28 '22 at 09:34
[See this on implementation merge sort using modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Aug 28 '22 at 09:46
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Aug 28 '22 at 10:12

john · Accepted Answer · 2022-08-28T06:55:49.723

2

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.

edited Aug 28 '22 at 06:55

answered Aug 28 '22 at 06:49

john

85,011
4
57
81

1

@ShahrukhAbrar understand `array1` and `array2` are not valid C++. C++ doesn't provide VLAs. – David C. Rankin Aug 28 '22 at 06:57
1

@DavidC.Rankin Just added -Werror=vla to my compiler args so I avoid using it. Thanks! – Shahrukh Abrar Aug 28 '22 at 08:24
While it would be better to use `std::vector`, you can allocate for the temp arrays since you are using the iterative mergesort and the lifetime of each is limited to the individual call to `merge()`. So you can `int *array1 = new int[n1];` (same for `array2`) and then `delete[] array1;` at the end of the function (ditto for `array2`). – David C. Rankin Aug 28 '22 at 09:11

score 0 · Answer 2 · answered Aug 28 '22 at 06:58

 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

MergSort won't sort the array

2 Answers2