Help in Merge Sort Algorithm

I am studying Merge Sort and have implemented the algorithm. Although I do understand it’s recursive nature and the flow, I do not understand how the recursive function is hitting the base condition since it is not mentioned in the code. I implemented this code with the help of other implementation of the same. I have written the comment about the line I am finding it difficult about it’s base condition being hit.
#include

using namespace std;

void Merge(int a[], int l, int mid, int r)
{
    int n1,n2,i,j,k;
    n1 = mid - l + 1;
    n2 = r-mid;
    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+1+j];
    i=0;
    j=0;
    k=l;
    while(i < n1 && j < n2)
    {
        if(L[i] <= R[j])
        {
            a[k++] = L[i];
            i++;
        }
        else if(R[i] <= L[j])
        {
            a[k++] = R[j];
            j++;
        }
    }
    while(i<n1)
    {
        a[k++] = L[i];
        i++;
    }
    while(j<n2)
    {
        a[k++] = R[j];
        j++;
    }
}

void mergeSort(int a[],int l,int r)
{
    if(l < r)
    {
        int mid;
        mid = (l+(r-1))/2;
        mergeSort(a,l,mid); // Once l < r is true it goes to the next function even though there is no return function written..
        mergeSort(a,mid+1,r);
        Merge(a,l,mid,r);
    }
}
int main()
{
    cout<<"Enter length of array: "<<endl;
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    cout<<"Elements before sorting: "<<endl;
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    mergeSort(a,0,n-1);
    cout<<endl;
    cout<<"Elements after sorting: "<<endl;
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

there is no need for return statement to be mentioned in the code for base case. This is because, in the base case , l<r will be false and the function wont be called for subsegments to be sorted first. Control wont even enter the if body.

1 Like

@montycs Once the condition is true yes it will go for the call of mergeSort again. It keeps on going like this and when you find the first entry(of l and r) for which l>=r (certainly it will be atleast it will be l==r) because you are decreasing the range by taking the mid=(l+r)/2 as r everytime.
At that time with given values of l ,mid,r Since the next call cannot occur, the function returns even without return statement because there is no statement to be executed next, once the condition l<r is not satisfied.
If a function return type is void you need not write return statement explicitly. You can check this here too.

http://www.cs.fsu.edu/~cop3014p/lectures/ch7/index.html

A function definition is limited to curly braces {} . As soon as compiler get the closing brace it remove the function call from stack.(I understood it that way…plz correct me if i m wrong).

Btw you have written " mid = (l+(r-1))/2; ". Shouldn’t it be (l+(r-l))/2 which is same as (l+r)/2 (only when we are dividing by 2).

Please let me know if i could not understand your question correctly.

1 Like

Very well explained bro!