MERGE SORT ALGORITHM

Merge sort is one of the best sorting Algorithm / Technique.

It is a “divide and conquer” based technique which is efficient in speed and reduced time complexity. It basically divides the problem in to two subproblems after every iteration and therefore, its time complexity is improved or we can say, increased drastically.

Let us understand the basic working of Merge Sort:

1. It follows divide and conquer approach
2. It keeps breaking the problem into two smaller sub problems and it continues doing that until the problem is left with only one element
3. In the end, we are left with two sorted arrays which are merged back as original array (Sorted)
4. This is how the whole divide and conquer process works.

While we compare the two sub-arrays for merging, We initially consider the first element as we sort in ascending order, element of lesser value becomes the next element of the sorted array. We repeat this procedure until both the sub arrays are empty and the resulting sorted array contains all the elements in sorted manner.

Pseudocode for MergeSort

• First initialise the right and left variables which marks the end index and start index of the array respectively.
• Suppose Length of array is N.
• We assign Left as 0 and right as N — 1.
• Find mid = (left + right) / 2
• Now we Call recursive mergeSort on (left , mid) and (mid + 1 , rear)
• We will continue till left < right
• In the end, we will call merge function which merges the last two sorted sub problems and returns a sorted array

MERGE SORT ALGORITHM:

MergeSort(array , left , right):

if left > right

return

mid = ( left + right ) / 2

mergeSort(array , left , mid)

mergeSort(array , mid + 1 , right)

merge(array , left , mid , right)

end

Example of Merge sort Algorithm:

Lets understand the working of merge sort using the above example (Image)

Assume size of array in N which in the above case is N = 6

So, after each step or iteration, The array of size N gets divided into two subarrays of size N / 2 until no further subdivision can be done.

In the first step, we have our array1 as 9 , 7 , 8

Now the array1 of size 3 is again divided into two sub arrays

S1 = 9 , 7

S2 = 8

Now S1 is again divided into two sub parts as 9 and 7. Since, now we are left with sub arrays of size 1 or singleton sarrays, the process of division for the left part stops here.

Now we start to merge these back in sorted order, The last 2 sub arrays are merged together in sorted manner using the procedure explained in the code and above, which forms a new array as 7 , 9. Going further, We merge the array containing 8 as element with this list giving us sorted left part as result.

Similary, the right part is also divides into sub arrays and then merged back into sorted subarrays. Which in the last iteration, gets merges as one whole sorted array.

Now let’s analyse the most important factor of any algorithm.

TIME COMPLEXITY OF MERGE SORT

BEST TIME COMPLEXITY: O(N logN)

AVERAGE TIME COMPLEXITY:O(N logN)

WORST TIME COMPLEXITY:O(N logN)

In the best case, we might be given an already sorted array which doesn’t need to sorted further.

In the worst case, we divide the problem into 2 subsequent subproblems in every iteration which will basically perform logN operations and these has to be done N times which results in total NlogN operations

SPACE COMPLEXITY OF MERGE SORT:

N auxiliary space is required in Merge Sort implementation as all the elements are copied into an auxiliary array

Space complexity is: O( N )

DIFFERENCE BETWEEN QUICK SORT AND MERGE SORT:

• Quick sort does not require any extra space as it works on the array itself using a pivot position. Whereas merge sort requires space to create subsequent subproblem arrays.
• IN MERGE SORT, we create two arrays at each iteration / step which ends up requiring extra space.
• IN QUICK SORT, we do not need to create any temporary arrays which is infact, helping in reducing the space complexity.
• Quick sort is definitely faster than merge sort but merge sort is more efficient and faster in case of large arrays or datasets.
• In case of stability, quick sort is less stable as many swapping operations need to be performed which reduces the overall stability of the algorithm whereas merge sort maintains the relative ordering of elements.

The down side of merge sort is that it requires additional space to store the sub arrays which makes it more space consuming and it also makes quick sort a more preferred algorithm as it does not require any extra space.

Comparing their efficiency, Merge sort is efficient and faster than quick sort in case of larger array size or larger data.