Hello all, I am confused with the recursion in Mergersort., i came across this C code and while trying to understand the recursion involved ,i added several trace statements to know he states of the variables. I am confused on the values retained in variables in a recursive call.
The array values are arr[]={2,3,5}. I am posting the code that recursively splits the array
int mergesort(int a[], int low, int high)
{
int mid;
printf("
low=%d high=%d
",low,high);
if(low<high)
{
mid=(low+high)/2;
printf("
before mid mid=%d high=%d,low=%d
",mid,high,low);
mergesort(a,low,mid);
printf("
before mid+1 mid=%d high=%d,low=%d
",mid,high,low);
mergesort(a,mid+1,high);
printf("
after mid+1 mid=%d high=%d,low=%d
",mid,high,low);
printf("
calling merge");
printf("
calling merge mid=%d high=%d,low=%d
",mid,high,low);
merge(a,low,high,mid);
}
return(0);
}
Now the output for this is:
low=0 high=2
before mid mid=1 high=2,low=0
low=0 high=1
before mid mid=0 high=1,low=0
**low=0 high=0
before mid+1 mid=0 high=1,low=0
**
low=1 high=1
after mid+1 mid=0 high=1,low=0
**calling merge
calling merge mid=0 high=1,low=0
before mid+1 mid=1 high=2,low=0**
low=2 high=2
after mid+1 mid=1 high=2,low=0
calling merge
calling merge mid=1 high=2,low=0
sorted array:
2
3
5
**low=0 high=0
before mid+1 mid=0 high=1,low=0:**I dont understand how the value of high is 1 as after computing mid the value sent is mergesort(a,0,0) and thus low is 0 and high must be 0?
calling merge
calling merge mid=0 high=1,low=0
before mid+1 mid=1 high=2,low=0: Here the merge function is passed with the following values merge(a,low,mid,high):merge(a,0,0,1) and after the function returns the next call to mergesort(a,mid+1,high) has the values of mid as 1,high as 2 and low as 0. I am stuck at the values of mid and high here??
Any explanation would be helpful. I hope there is some clarity in my doubts. Thanks
