Recursion problem

Given below is a function which is part of a bigger program implementing Merge Sort http://linux.wku.edu/~lamonml/algor/sort/merge.html

Code:

---


void merge_sort(int a[], int low , int high) //a
 {
  int mid;
  if(low<high)
    {
    mid=(low+high)/2;
    merge_Sort(a,low,mid)//b;
    merge_Sort(a,mid+1,high);//c
    simple_merge(a,low,mid,high); //d
    }
}

---

Now I cant figure out the way this recursion is working . According to me there would be infinite number of calls made between "a " and "b" .

Let us take array 5,8,10 we pass at first merge_sort(a,0,2). mid becomes 1 so b calls a with low=0 and high = 1. Next mid becomes 0 and b calls a with low=0 and high =0 . This time low=high and the "if condition" is false , mid will be 0 and will continue to be 0 and hence "b" will go on calling "a" . But the program actually works perfectly , so where am I wrong in my tracing of the program?

When low and mid are both zero, they enter that function, which immediately returns because low is not less than high.


Quzah.

ok , if that happens "c" and "d" won't be executed as the block following if will be skipped.

No, they'll still execute also, but in all of those instances "less" isn't, so they each in turn return. Consider:

Code:

---

if( low{0} < high{1} )
{
    mid = high / 2 {0};
    fun( a, {0}, {0} ) -> gets to "if 0 < 0" ... so that one returns (this is b)
    fun( a, {1}, {0} ) -> gets to "if 1 < 0" ... so that one returns (this is c)
    sim( a, {0}, {0}, {1} ) -> is d, whatever that is...

---

Everything here ins {} is just an illustration of the value being passed, not actual intended code.


Quzah.