Two recursive calls in a Merge Sort function confusion

Question

I have been out of touch with Algorithms for a while and have start revising my concepts these days. To my surprise the last i remember of my recursions skill was that i was good at it but not anymore. So, i have a basic question for you guys which is confusing me. Please see the below code first ..

private void mergesort(int low, int high) {
    if (low < high) {
        int middle = (low + high)/2 ;
        System.out .println ("Before the 1st Call");
        mergesort(low, middle);
        System.out .println ("After the 1st Call");
        mergesort(middle+1, high);
        System.out .println ("After the 2nd Call");
        merge(low, middle, high);
    }
}

The function call

mergesort(0,7);

And the output is

Before the 1st Call

Before the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 2nd Call

After the 1st Call

Before the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 2nd Call

After the 2nd Call

The thing confusing me in the above code and result is the second recursive call. I am understanding the flow until the fourth output line ( i.e : After the 1st Call). But i cannot understand why does it outputs ( After the 2nd Call ) after the ( After the 1st Call ). According to whati am understanding from the code After the output ( After the 1st Call ) the mergesort function with parameter (middle+1, high) should be called and it should output ( Before the 1st call ) and go into the recursive call with mergesort (low, middle). I am comfartable with one recursive call functions and understand and am sync with foreg fibonacci example .

Answer 1

On the fourth output line, you have returned from the first call and the subsequent 2 recursive calls, so now control reaches the System.out .println ("After the 1st Call");

So, the condition low < high is false after the second recursive call, so you just exit the function. Then, control returns to the line right after the second recursive call.

TIP One thing I used to do when learning recursion is to keep track of stack depth (e.g. pass in a parameter for this) and then on your output you indent your output based on stack depth. This helps you visualize where you are in the recursive chain, and makes debugging easier.

So your debugging input could look similar to the following:

entered method, low = 0, high = 10
  entered method, low = 0, high = 5
     entered method, low = 0, high = 2
     exiting method, low = 0, high = 2
  exiting method, low = 0, high = 5
exiting method, low = 0, high = 10

Answer 2

Just follow the execution...

First call 0,7 --> enters if, middle = 3 (integer division), calls again as (0,3)
Second call 0,3 --> enters if, middle = 1, calls again as (0,1)
Third call 0,1 --> enters if, middle = 0, calls again as (0,0)
Fourth call 0,0 --> does not enter if, back to third call
Third call 0,1 --> calls as middle+1,high which is (1,1)
Fifth call 1,1 --> does not enter if, back to third call
Third call 0,1 --> calls the string you didn't expect

can continue on but that is where the string you aren't expecting is executed.

Answer 3

You could print out the values of high and low too. It would be much easier to follow the recursion.

Answer 4

Try printing the value of the middle variable.

Best practise dictates that you don't code in "Before function" style debugging messages without any variable output.