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..... :(

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.

## All 6 Replies

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.

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.. :(

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.

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 ?

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

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 :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.