CODEWITHSUNDEEP
javamergesort
Seinfeld
Seinfeld

Reputation: 433

Merge sort recursion call explanation in Java

I understand the point of recursion and how it works in very simple cases, E.G

// Make a func that that will add factorials

public long fact(long n){
  if(n <= 1)
    return 1;
  else
    return n * func(n-1)
}

I can see that n decreases with every call and in case if n = 5 the output will be 120. In this case, I understand how recursion works.

However, when it gets to a little more complex calls, I can't really see what's happening behind the scenes. I can usually understand the code, but would not be able to explain someone why or how is it happening. E.G

public void mergeSort(int[] list, int lowIndex, int highIndex){
        if(lowIndex == highIndex)
            return;
        else{
            int midIndex = (lowIndex + highIndex) / 2;
            mergeSort(list, lowIndex, midIndex);
            mergeSort(list, midIndex+1, highIndex);
            merge(list, lowIndex, midIndex, highIndex);
        }
    }

I can not figure out how this recursive mergeSort calls return what they return.

If we assume that lowIndex = 0 & midIndex = 5, what does this method do ?

If someone has some other examples that give good hints in this learning process, that would work nicely as well : )

Upvotes: 2

Views: 1355

Answers (3)

Radioactive
Radioactive

Reputation: 769

Merge Sort is a divide and conquer algorithm which divided the entire array into two halves and then keeps dividing unless there is a subarray which contains only two elements.The algorithm then goes ahead and merges the sub-array that contains one element after sorting them. The recursion call stack of the merge sort however is a little hard to grasp at the first go.

Lets say, we have an array 4,0,6,1,5,2,3

Now as per your code above,

Midindex = 3

The first merge sort recursion calls

(list, 0, 3) When this goes back, since it is recursion and satisfies the base case, 0<3,

we have , midindex = 1 so next call is (list,0,1)

Again, when this is called, recursively, since 0<1, we have midindex = 0

so next call is (list,0,0) this call fails the base case,

So we go to the next line in the code which is (list, mid+1, high) this call interprets as (list,1,1) [ Since, as per the above flow, mid was 0] again list,1,1 fails the base case, so we move down the code below which is merge(list, low,mid,high) In this case, this is (list,0,0,1)

If you further see the code for merging, you will see that it sorts the subarray and then merges it. In this case, since it is 4,0

So the subarray after merging would be 0,4.

This is the completion of the first recursion stack which is nothing but the left side of merge(0,3)

After this the control goes back to completing the right side merge of 0,3 Midindex = 1 So merge sort(list,mid+1,high) [since merge sort(list, low,mid) is already complete above). This further goes down to, mergesort(list,2,3) again calling the recursion base case, since 2<3 mid = 2 so, merge sort(list,2,2) and similarly, mergesort(list,3,3). Both these calls will fail the base case and merge function will be called. This way the recursion stack gets repeated, the final result is a beautiful sorted array. I hope I am clear. enter image description here

Upvotes: 0

Jul10
Jul10

Reputation: 503

I assume you know how the merge logic works.
When you hit the first call of mergeSort(lowIndex,midIndex), it recalls itself many many times until it will work with a subarray of lenght 2, easy to order ( they need only a comparison).
At this point mergesort(0,1) has been completed and it's time to execute mergesort(2,3) that will return another ordered subarray of length 2; then now in the merge function these subarrays are compared and merged. So the method ends returning to from where it was called ( in this case from mergesort(0,3) ) and so the next statement to execute is mergesort(4,7).
Considering N the lenght of the unordered array,the process is repeated until you go back to the top call where the two subarrays of lenght N/2 (or N/2 and N/2 -1 if N is odd) are merged.

Upvotes: 1

Bohemian
Bohemian

Reputation: 424983

This method doesn't return anything. Rather, it manages the divide-and-conquer part of the logic and calls merge(), which does an in-place sort of the (sub)array, mutating it.

Upvotes: 0

Related Questions