Hey coder. How have you been? Let's discuss the concept, "Merge Sort". Have a look at the problem statement first.

**Important Links : Problem Link, Solution Video**

Merge sort

Hey coder. How have you been? Let's discuss the concept, "Merge Sort". Have a look at the problem statement first.

**Important Links : Problem Link, Solution Video**

Problem Discussion :

You are given an array(arr) of n integers and have to sort the given array in increasing order using the merge sort.

In the previous question you have already done "Merge two Sorted Arrays".

That concept is going to be used in Merge Sort so if you haven't watched that video already, do it now.

Approach :

This is a recursive program.

Let's assume the array to be sorted is [7, 4, 1, 3, 6, 8, 2, 5].

We divide this array into 2 parts as can be seen in Figure 1.

The first part is 7,4,1,3 and the second part is 2,5,6,8.

Reader, do you remember that we always keep faith in recursive questions?

So by keeping faith, we know that if we divide the array in 2 parts then each part of the array will return itself as a sorted array.

In figure 1, we have faith that if we call the function on 7,4,1,3 recursively then it will return 1,3,4,7 and similarly 6,8,2,5 will return 2,5,6,8.

Now we already know how to merge 2 sorted arrays. Hence we merge both the sorted arrays that we got from the 2 parts that are 1,3,4,7 and 2,5,6,8 to get a new merged and sorted array 1,2,3,4,5,6,7,8.

RECURSION TREE

In figure 2, you can notice that a recursion tree is made in which each array is divided into 2 arrays till the last array has only 1 element left and can't be divided further.

EULER PATH

Now that we have seen the recursion tree, let's also see how we traverse through it. The Euler path can be shown highlighted in green.

We go up the levels from the unsorted array 7,4,1,3,6,8,2,5, and reach the last level that contains a single element array 7. When we reach there, a new array storing 1 element '7' is returned to the previous array 7,4. Here, the path falls back on the previous level and the last level is popped from the stack.

As the Euler path then moves up a level again, the new level gets pushed into the stack once again. Again a new array with element '4' is returned.

Now that we fall to the post area of 4, the 2 sorted arrays 7 and 4 are merged, and a new array containing 4,7 is returned.

This Euler path keeps on sorting 2 arrays, merging them and then returning them to the previous level .

Doing this recursively, when we finally reach the first level, we have 2 sorted arrays 1,3,4,7 and 2,5,6,8 which are merged and as the stack goes empty the final answer 1,2,3,4,5,6,7,8 is returned.

We highly recommend you to watch the video "Merge Sort"[1:38-3:45] for a better understanding of this traversal.

Have a look at the following code and then we'll discuss it step by step.

import java.io.*;
import java.util.*;
public static int[] mergeSort(int[] arr, int lo, int hi) { //1
if(lo==hi){ //2
int[]ba=new int[1];
ba[0]=arr[lo];
return ba;
}
int mid=(lo+hi)/2; //3
int[] f=mergeSort(arr,lo,mid); //4
int[] s=mergeSort(arr,mid+1,hi); //5
int[] fin=mergeTwoSortedArrays(f,s); //6
return fin; //7
}

java; true";

CODE DISCUSSION

- We pass the given array to be sorted, lo and hi as parameters to the function mergeSort. Here lo is the index 0 at the beginning of the array and hi is the index arr.length-1 at the end of the array.
- Base Case: If at any time lo and hi cross each other then an array of size 1 is formed and stores the element at lo (or hi) .This array is then returned.
- Now, we find the mid value of the array to split our unsorted array into 2 halves.
- Then we recursively call the function mergeSort on the first array, which then returns us a sorted array (By our Faith).
- Similarly we recursively call the function mergeSort on the second array, which then returns us a sorted array (By our Faith).
- When we have 2 sorted arrays available to us, we merge them together to give us a single sorted array as we already know from the previous question of "Merge 2 Sorted Arrays".
- Now that we have this merged sorted array with us we return it as the answer.

Analysis

Time Complexity :

**O (nlogn)**

Since merge sort keeps dividing the array into two halves and taking linear time to merge these two halves hence the time complexity is of order nlogn.

SPACE COMPLEXITY :

** O (n)**

Since 1D arrays are used to store numbers, therefore the space complexity is linear.

With this we conclude our topic of Merge Sort. If you have any doubts in this section, we suggest you reread it again after some time and make the recursive tree by hand for better practice. Till then, Goodbye !