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.
Assume an unsorted array:
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.
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.
We will now further divide this array into a level where they can no further be divided.
In the next step, we will combine these elements but in a sorted manner.
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.
The final step is to combine these two arrays into one single array with sorted elements.