recursive merge sort, how does it work?
hey friends
I am stuck up with the code of recursive merge sort and am unable to understand as to how is the recursion working. Im posting the code for the merge sort and telling the details of where im facing the problem, if someone could explain me with an example as to where does the control go.
im not posting the working code but just the part where im facing confusion.
void mergesort(int[] a,int[] tmpa,int left,int right)
{
if(left<right)
{
int center=(left+right)/2;
mergesort(a,tmpa,left,center);//1
mergesort(a,tmpa,center+1,right);//2
merge(a,tmpa,left,center+1,right);
}
}
plz explain as to how is the control being transferred in the two recursive calls labelled 1 and 2 in the above code. take for eg a series
4,2,5,7,1,8 to be sorted
thanks.>
> hey jack
>
> i understand the concept as to how does merge sort
> work but im having problem figuring out the recursie
> calls. how are they working
>
> if you can help
What do you mean, "How are they working"? What part don't you understand? If you understand how mergesort works in the abstract, you should be able to see how that Java code is a direct expression of that.
You mergesort an array by mergesorting the left half and mergesorting the right half and then merging the results.
i am having trouble figuring out these two sttements in the code
mergesort(a,tmpa,left,center);//1
mergesort(a,tmpa,center+1,right);//2
ie the recursive calls. when will the //2 be executed? . what will be the values of center+1,right at which it starts executing ?
basically im having trouble with the recursive calling. i have had read the tutorials but those are for simple cases like factorial etc. if someone can explain this in detail
thanks
> i am having trouble figuring out these two sttements
> in the code
> mergesort(a,tmpa,left,center);//1
> mergesort(a,tmpa,center+1,right);//2
>
> ie the recursive calls. when will the //2 be
> executed?
After //1.
>. what will be the values of center+1,right
> at which it starts executing ?
Print them out or use a debugger to see for yourself. Better still, try to work through it by hand first and then use the print statements or debugger to see if you were right.
> basically im having trouble with the recursive
> calling. i have had read the tutorials but those are
> for simple cases like factorial etc. if someone can
> explain this in detail
It's the same priniciple. You start with the big piece, make a recursive call an a part of it, make a recursive call on a part of that, and so on. Ultimately, you get down to the smallest piece--the stopping condition--and you do the simple operation on that the results of that feed back up to the previous call, and its results feed back to the one before that, and so on until the second call's results feed back to where you called it on the whole thing.
It's really probably much easier to observe than to try to understand from an explanation though.
