Merge Sort

Merge sort divides the array into two halves and then combines them in a sorted manner. The concept of Divide and conquer is followed in the Merge Sort. An array is divided into two equal sub-arrays; these sub-arrays are sorted first and then merged to form a final sorted array.


The divide and conquer rule:

Step1: the problem is divided into sub-problems. Problem being the final array and sub-problems being the sub-arrays.

Step2:  Solve the sub-problems, i.e, sort the sub-arrays.

Step3: Merge the sorted sub-arrays to form a final array.


 

Working:

Assume an unsorted array:

merge sort example

Now, the next time, you need to divide the array into two equal halves. As we have an array of 8, we will divide it into 4 each.

merge sort example

dividing the array into two equal parts does not change the sequence of appearance. So we further divide the array into equal units of 2 each.

merge sort example

We will now further divide this array into a level where they can no further be divided.

merge sort example

In the next step, we will combine these elements but in a sorted manner.

merge sort example

Out of these, we will combine them to make the two units or arrays of equal size. While combining, we will consider the sorting by placing the lowest element first.

merge sort example

The final step is to combine these two arrays into one single array with sorted elements.

merge sort example