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!