Two recursive calls in a Merge Sort function confu

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

Go to eclipse debug tool. Follow the step and you will find the rule double recursion. Thats what I do.

Answer 2

Merge Sort uses a recursive algorithm to create a complete binary tree with a height of Log N, being N the number of nodes of that tree (this is why is so efficient). In the next image you can see step by step what is the flow of execution of this algorithm for your case, with the binary tree that is created (which I think is the best way to understand how it works):

Binary tree that is generated using Merge Sort with an array of 8 positions

What Merge Sort does is to split the array in halves recursively, going first to the lowest halves until we reach one unitary element, and then go and split the higher ones from the lowest element recently reached. This is why it calls itself two times per each previous call, in order to create a complete binary tree that stops when we reach one unit (with leaf nodes) and only merge when we have two (with parent nodes). In the following image you can see how your array is split recursively, step by step:

Step by step division of an array of 8 elements using Merge Sort

Answer 3

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

Answer 4

The indentation in the following corresponds to the recursion:

mergesort(0, 7)
    middle=3
    "Before the 1st Call"
    mergesort(0, 3)
        middle=1
        "Before the 1st Call"
        mergesort(0, 1)
            middle=0
            "Before the 1st Call"
            mergesort(0, 0)
                (0 < 0) is false so return
        "After the 1st Call"
        mergesort(1, 1)
            (1 < 1) is false so return
        "After the 2nd Call"

        etc ...

Answer 5

Run this piece of code to understand recursion well.I have considered the stack depth in the console.Hope it makes it easy to understand!

    #include "stdafx.h"
    #include <iomanip>
    using namespace std;
    static int stackdepth=0;
    void mergesort(int[],int,int);
    void merge(int[],int,int,int);
    void  space(int);
    int main(int argc,char *argv[])
    {
        int a[8]={5,7,1,4,9,3,2,0};
        mergesort(a,0,7);
        for(int i=0;i<10;i++)
    //  cout<<a[i]<<endl;
        return 0;
    }
    void mergesort(int a[],int low,int high)
    {
        int mid;

        if(low<high)
        {

            mid=(low+high)/2;
            space(stackdepth);
            cout<<"First Recursion Enter";
            cout<<" Low :"<<low<<" Mid :"<<mid<<endl;
            stackdepth++;
            mergesort(a,low,mid);
            stackdepth--;
            space(stackdepth);
            cout<<"First Recursion Exit";
            cout<<" Low :"<<low<<" Mid :"<<mid<<endl;
            space(stackdepth);
            stackdepth++;
            cout<<"Second Recursion Enter";
            cout<<" Mid+1 :"<<mid+1<<" High :"<<high<<endl;
            mergesort(a,mid+1,high);
            stackdepth--;
            space(stackdepth);
            cout<<"Second Recursion Exit";
            cout<<" Low :"<<mid+1<<" High :"<<high<<endl;
            space(stackdepth);
            cout<<"Merge Low :"<<low<<" Mid :"<<mid<<"High :"<<high<<endl;
            merge(a,low,mid,high);
            cout<<endl;
            space(stackdepth);
            cout<<"------------------------------------------------------------------------------------------"<<endl;
        }
    }
    void space(int stackdepth)
    {
        for(int i=0;i<stackdepth;i++)
        cout<<"                     ";

    }
    void merge(int a[],int low,int mid,int high)
    {
    //  cout<<endl;
    //  cout<<"Merging Begins"<<endl;
        int b[8];
        int i,k,j;
        i=low;k=low;j=mid+1;
        while(i<=mid && j<=high)
        {
            if(a[i]<a[j])
            {
                    b[k++]=a[i++];
            }
            else
            {
                b[k++]=a[j++];
            }
        }
        while(i<=mid)
            b[k++]=a[i++];
        while(j<=high)
            b[k++]=a[j++];
        space(stackdepth);
        for(int i=low;i<=high;i++)
        {
            a[i]=b[i];
        cout<<a[i]<<" ";
        }
            //cout<<"Low :"<<low<<" Mid :"<<mid<<" High :"<<high<<endl;
        //  cout<<"Merging Ends"<<endl;
        //  cout<<endl;
    }

Answer 6

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.