recursion confusion@binary search + merge sort

[somjit{}]

the code works perfectly, just i got something i dont understand...

i'v been trying to get a hold of recursion and sorting for about 3-4 days now, im getting some of it, but still not happy enough..

i searched for some good code for binary search and merge sort on the net, found some, took the one i liked most, and have been editing it to my needs. it would have felt a lot better had i been able to write both on my own,
but....
i cant..... :(
(hence all the downloading, editing and testing and comparing ... :| )

well , i have two codes:

1. the main binary search code
2. the merge sort one, saved as a header file and called from binary search one...

works perfectly, even after all my edits... this is the output......

here is the part of the code that generates it:

void partition(int arr[],int low,int high){

    int mid;
    static int count=0;
    printf("inside partition, for this step>> low : %3d    &   high : %3d  , step number: %d\n",low,high,count++);
    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }

}

the array consists of random numbers (generated via srand(), and rand() inside a for() loop, thus saving me time), and this array is passed to the partition() function contained in my merge-sort header file. everythings fine, just one confusion regarding the output:

i dont understand why i get output for cases (step number: 3,4,5 and 8,9,10) when "low" and "high" are equal, where as the if() condition in the partition() block states recursion only when low<high...

i worte the printf() line in partition() just to understand how the recursion was taking place, and this thing... i tried , but couldnt understand...

this is my full mergesort header file:

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

void partition(int arr[],int low,int high){

    int mid;
    static int count=0;
    printf("inside partition, for this step>> low : %3d    &   high : %3d  , step number: %d\n",low,high,count++);
    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }

}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
        for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
        for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}

also,
links to the original codes: binary search , merge sort

link to my edited code: binary search ( i didnt want to clutter up the post too much, so just put the link here instead of pasting it ... i hope im not violating any rules...)

learned lots from daniweb in these few weeks... hoping to learn more once again :)

thanks..
somjit :)

p.s: i ended up adding two attachments by mistake, both are same, one's just a crop version of the other... i apologize for any trouble it may cause.

[deceptikon]

i dont understand why i get output for cases (step number: 3,4,5 and 8,9,10) when "low" and "high" are equal, where as the if() condition in the partition() block states recursion only when low<high...

That might be confusing if your output were performed inside the if statement's body, but it's not. So regardless of the values of low and high, you're still printing output; the two are unrelated.

[somjit{}]

but it's not. So regardless of the values of low and high, you're still printing output; the two are unrelated.

the printf() might not be inside if(), but if() states the condition when partition() will be called (recusrsively).. so doesnt that make the printf() dependent on if() ?

i know the solution might be pretty simple, but i cant seem to understand it.. :(

[deceptikon]

the printf() might not be inside if(), but if() states the condition when partition() will be called (recusrsively).. so doesnt that make the printf() dependent on if() ?

It does, but you're thinking of things in the wrong order. When low and high are equal, the printf() still executes even though the contents of the if statement do not.

[somjit{}]

When low and high are equal, the printf() still executes even though the contents of the if statement do not.

lets take : low = 0 , high = 1;

**low<high?** yes

    thus, mid =0 (  (0+1)/2  )
    partition(array, low=0, mid=0) called.. // this is for the recursive division of the left block of the array

        **low=0 and high=0 printed**
         going into if() block... 
                                      **low<high** ? ans: no... (low=high=0 here)
                                      no more partion() calls
                                      end of left block recusrcive division


also, when low = 0 , high = 1, mid=0; 
    partition(array, (mid+1=1), high=1) called      //this is for the recursive division of the right block of the array

         recusrsion is now called with low=1, high=1
            1,1 should be printed.... 

                going into if()...

                                    **low<high** ? ans: no... (low=1 high=1 here)

                                    no more partion() calls
                                    end of right block recusrcive division

this is how the flow of the code seems to me.. but i dont get how all those low=high cases gets printed... you said printf() still executes even when low<high doesnt hold... i can understand that part occuring once, for each of left and right block division... in the case when 0,0 and 1,1 gets printed. but after that, why didnt the whole iteration stop ?

[somjit{}]

oh ..no...! i think im getting it....

[somjit{}]

got it!!! yay! :D

entering condition: l=0,h=5,mid=2

left block:                                                      right block:
  partition(arr,0,2)  {takes 0,2 to next iteration, prints it}     partition(arr,3,5) {takes 3,5 to next iteration, prints it}

    L: partition(low=0,mid=1)   R:partition(mid+1=2,2)               L: partition(3,4)        R:partition(5,5)  

        {this goes on to          {this loop terminates              {this makes                  {terminates with printing 5,5}
        make further calls          by printing 2,2}                  another call
        affecting both L,R blocks}                                    affecting L,R blocks again}              
        .                             .                                     .               .   
        .                             .                                     .               .

        so on...

thus, each left and right block division also has an effect on the other block... resulting in the printing of the low=high terms.

i got it :)

thanks for pointing out the key @deceptikon :)