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