Merge Sort

The basic idea is that we divide the given ‘ARR’ into two-part call them ‘leftHalves’ and ‘rightHalves’ and call the same function again with both the parts. In the end, we will get sorted ‘leftHaves’ and sorted ‘righthalves’ which we merge both of them and return a merged sorted ‘ARR’.

We implement this approach with a divide and conquer strategy.

Here is the algorithm : 

1. Divide ‘ARR’ into two-part ‘leftHalves’ and ‘rightHalves’ and the size of both parts are almost equal means ‘leftHalves’ can have one size extra comparing to ‘rightHalves’
   • Recursively solve for ‘leftHalves’
   • Recursively solve for ‘rightHalves’
2. In the recursive part, every time we will get some part of ‘ARR’. Then divide it into two parts until the size of each subarray is not equal to 1.
3. In the return part, we get two sorted arrays ‘leftHalves’ and ‘rightHalves’ using recursion.
4. After getting both sorted parts, we merge both of them in such a way so that we get a merged sorted array.

MERGE() function :

1. Suppose we have two sorted arrays ‘leftHalves’ and ‘rightHalves’ then we merge both of them into ‘mergedArr’
2. Currently, we have two pointers ‘ptrLeft’ and ‘ptrRight’, and both are pointing to starting indices of ‘leftHalves’ and ‘rightHalves’.
   • If ‘leftHalves[ptrLeft] < rightHalves[ptrRight]’ then add ‘leftHalves[ptrLeft]’ in ‘mergeArr’ and increase ‘ptrLeft’ by one.
   • Else add ‘rightHalves[ptrRight]’ in ‘mergeArr’ and increase ‘ptrRight’ by one.
3. Add remaining elements from ‘leftHalves’ and ‘rightHalves’.
4. Copy ‘mergeArr’ elements to ‘ARR’.

The basic idea is that consider every element of ‘ARR’ as a sorted array of size 1.

Consider given ‘ARR’ : { 8, 3, 4, 6, 1, 5, 7, 2 }

In the first step, merge all the elements of  ‘arr’ with a gap of ‘1’ indices so that every element of gap ‘1’ indices become sorted in size of ‘1’ subarray. At the end of this, we will get { 8, 3, 4, 6, 1, 5, 7, 2 }. In the second step, merge all the elements of ‘ARR’ with the gap of ‘2’ indices in the way every element of gap ‘2’ indices are sorted. At the end of this, we will get { 3, 8, 4, 6, 1, 5, 2, 7 } and you can see every pair of size ‘2’ is sorted. In the third step, merge all the elements of ‘ARR’ with the gap of ‘4’. At the end of this, we will get { 3, 4, 6, 8, 1, 2, 5, 7 } and you can see every pair of size ‘4’ is sorted { 3, 4, 6, 8 } and { 1, 2, 5, 7 }. In the fourth step, merge all the elements of ‘ARR’ with the gap of ‘8’ indices. At the end of all step, we will get a sorted ‘ARR’ { 1, 2, 3, 4, 5, 6, 7, 8 }.

Here is the algorithm :

1. Create a variable (say, 'currentGap') and initialize it to 2. In every iteration, we try to sort every part of size ‘currentGap’ and consider ‘nearestPowerTwo’ is the nearest number which is a perfect power of 2 and also greater or equal to the size of ‘ARR’
2. Iterate a loop until ‘currentGap’ is less than or equal to the ‘nearestPowerTwo’.
   • Divide the ‘ARR’ into ‘N/currentGap’ parts call it ‘curPortion’.
     • Divide every part into 2 half and sort them with help of intermediate ‘mergeArr’, in which we store sorted ‘curPortion’, and ‘ptrLeft’ points to the starting indices of this part and ‘ptrRight’ points to the middle part of this part and ‘end’ points to the end of this part.
       • Add current minimum value to ‘mergeArr’
         • If ‘ARR[ptrLeft] is smaller than ARR[ptrRight]’ then add ‘ARR[ptrLeft]’ in ‘mergeArr’ and increase ‘ptrLeft’ by one because we are maintaining ‘mergeArr’ sorted so we first insert smallest value.
         • Else add ‘ARR[ptrRight]’ in ‘mergeArr’ and increase ‘ptrRight’ by one.
       • At the end of this ‘curPortion’ place all the element again in ‘ARR’ so ‘ARR’ become sorted from ‘ptrLeft’ to ‘end’
3. Repeat the same step for the next part.
4. In the end, we will get a sorted ‘ARR’ and finally, return ‘ARR’