Mergesort recursion Help in C

[touches]

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("\nlow=%d high=%d\n",low,high);
if(low<high)
{
mid=(low+high)/2;

printf("\nbefore mid mid=%d high=%d,low=%d\n",mid,high,low);

mergesort(a,low,mid);

printf("\nbefore mid+1 mid=%d high=%d,low=%d\n",mid,high,low);

mergesort(a,mid+1,high);

printf("\nafter mid+1 mid=%d high=%d,low=%d\n",mid,high,low);

printf("\ncalling merge");

printf("\ncalling merge mid=%d high=%d,low=%d\n",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

[Salem]

Write it as

int mergesort(int a[], int low, int high,int depth)
{
int mid;
printf("\nlow=%d high=%d\n",low,high);
if(low<high)
{
mid=(low+high)/2;

printf("\n(%d) before mid mid=%d high=%d,low=%d\n",depth,mid,high,low);

mergesort(a,low,mid,depth+1);

printf("\n(%d) before mid+1 mid=%d high=%d,low=%d\n",depth,mid,high,low);

mergesort(a,mid+1,high,depth+1);

printf("\n(%d) after mid+1 mid=%d high=%d,low=%d\n",depth,mid,high,low);

printf("\n(%d) calling merge");

printf("\n(%d) calling merge mid=%d high=%d,low=%d\n",depth,mid,high,low);

merge(a,low,high,mid);
}
return(0);
}

Pass 0 as the depth when you call it from main.

[touches]

@Salem

Thanks for the help you suggested by using a depth variable. Now i almost get it. I have one doubt though after the first call to void merge(); do the values get reset(i.e) before calling merge() the value of the depth variable was 1 and after calling merge() the value becomes 0 . Am i correct in thinking that after the first call the values sent to the merger_sort() are the old values instead of the values got by recursively splitting the array in the previous calls of merge_sort()???

[MK27]

@Salem

Thanks for the help you suggested by using a depth variable. Now i almost get it. I have one doubt though after the first call to void merge(); do the values get reset(i.e)

No, what would that accomplish?

before calling merge() the value of the depth variable was 1 and after calling merge() the value becomes 0.

It's not clear exactly how the specific functions work in your example, since you didn't post them (maybe you should), but it appears to me that rather than having the function calls occur recursively (which they would in a real sort), this program demonstrates the sort by calling the functions manually a predetermined number of times (appropriate to the array size).

Am i correct in thinking that after the first call the values sent to the merger_sort() are the old values instead of the values got by recursively splitting the array in the previous calls of merge_sort()???

Again, would that not defeat the whole purpose? The idea is that merge_sort() splits the array in half each time, then merge() puts it back together. And the order of the number necessarily changes -- reseting the array would not make sense.

There is a great animated gif of merge sorting the numbers 1-8 here:

File:Merge-sort-example-300px.gif - Wikipedia, the free encyclopedia, from the article: Merge sort - Wikipedia, the free encyclopedia, which has further examples/diagrams/explanations.

In that animated gif, merge_sort() would be called on the 8 member array once, splitting it into two four member arrays, then two more times recursively to split each four member array into 2 member arrays. You can optimize at this point to return a sorted 2 member array, altho that is not quite what happens in the pseudocode in the article (it splits until there is only one element and returns it). Then merge() combines each two member array into a four member array, then a final merge() creates the sorted 8 member array. How merge() combines the array works is easy to understand if you watch the animation.

[touches]

@MK27

Yes the thought of resetting the values would defeat the purpose but i dont get how the values are stored in the recursive calls. I am posting the code and the output

array={4,1,7,3};

int mergesort(int a[], int low, int high,int depth)
{
int mid;
printf("\nlow=%d high=%d\n",low,high);
if(low<high)
{
mid=(low+high)/2;

printf("\n(%d) before mid mid=%d 

high=%d,low=%d\n",depth,mid,high,low);

mergesort(a,low,mid,depth+1);

printf("\n(%d) before mid+1 mid=%d 

high=%d,low=%d\n",depth,mid,high,low);

mergesort(a,mid+1,high,depth+1);

printf("\n(%d) after mid+1 mid=%d 

high=%d,low=%d\n",depth,mid,high,low);

printf("\n (%d) calling merge",depth);

printf("\n (%d) calling merge mid=%d 

high=%d,low=%d\n",depth,mid,high,low);

merge(a,low,high,mid);
}
return(0);
}

Output:

low=0 high=3

(0) before mid mid=1 high=3,low=0

low=0 high=1

(1) before mid mid=0 high=1,low=0

low=0 high=0

(1) before mid+1 mid=0 high=1,low=0

low=1 high=1

(1) after mid+1 mid=0 high=1,low=0

 (1) calling merge
 (1) calling merge mid=0 high=1,low=0

(0) before mid+1 mid=1 high=3,low=0

low=2 high=3

(1) before mid mid=2 high=3,low=2

low=2 high=2

(1) before mid+1 mid=2 high=3,low=2

low=3 high=3

(1) after mid+1 mid=2 high=3,low=2

 (1) calling merge
 (1) calling merge mid=2 high=3,low=2

(0) after mid+1 mid=1 high=3,low=0

 (0) calling merge
 (0) calling merge mid=1 high=3,low=0

sorted array:
1
3
4
7

Here i would like to know how the depth variable becomes 0 after returning from calling merge()??

[MK27]

Here i would like to know how the depth variable becomes 0 after returning from calling merge()??

Because it is recursive. Consider this:

#include <stdio.h>

void recurse (int a) {
	if (!a) return;
	recurse(a-1);
	fprintf(stderr,"%d\n", a);
}

int main(int argc, const char *argv[]) {
	recurse(5);
	return 0;
}

The initial call to recurse() sets a as 5, then the recursion counts down to zero. But notice that the output does not occur until the recursive calls return. So do you think this will print:

5 4 3 2 1

or

1 2 3 4 5

If you guessed the first one, you're wrong. Try it and think about why; the depth count in your merge_sort() does the same thing.

Recursive functions complete in reverse order; the first one to complete is the last one called, and the last one to complete is the first one called.

[touches]

@MK27

Thanks a lot for that snippet. It brought back memories of reading recursive function calls . Now i get why it acts the same in merge sort. Thanks a lot once again