Merge Sort-Approach & Analysis 💡

Merge Sort

Now , In order to understand the Merge Sort Algorithm , one should be aware of how to merge two sorted arrays first , as this will act as a helper function during the algorithm & it is always better to understand anything chunk by chunk rather than just mugging up the proposed solution !

The problem statement is that :

• given two sorted arrays(a,b) of integers.
• merge them and form one sorted array.
• it is to be done in a linear time complexity.

what we will be using is a two pointer technique here ! 💡

Step 1 : maintain two pointers let say i , j & initialize them to 0

Step 2 : keep the i pointer on the starting element of array 1 & j on the first element of array 2

Step 3 : Initialize a new array of size = size of array1 + size of array 2

Step 4 : while the i pointer reaches to the end of the array 1 or j reaches to that of array 2 , keep iterating the arrays and compare elements & always keep the smaller element from the too of the elements from both the array.

Step 5 : if any of the pointer reaches to the end , break the complete loop i.e while loop in this case & copy the remaining elements from array 1 or array 2, depending upon the situation that which array is fully iterated first.

Below is the sample example depicting the overall process discussed above :

So , by continuing making these greedy decisions , and taking the smaller element from both of them we can obtain a sorted array as you can see in the below image :

So , once we have an understanding of this , it is easy to learn merge sort , so let’s directly jump into the algorithm :

APPROACH :

Consider the following array: [7, 4, 1, 3, 6, 8, 2, 5]. As seen in Figure , we partition this array into two halves.

So we divide the array recursively by having a faith that each part will return a sorted array , as seen in the image below :

Dividing array Recursively left & right to obtain sorted array

You’ll observe that each array is divided into two arrays until the last array has only one element remaining and can’t be divided any more.

Recursive tree depicting left & right merge sort calls

Below is the Java code showing the implementation part of merge sort :

Merge Sort Method that divide array in left and right & obtain the sorted array by calling the merge two sorted arrays.

Merge two sorted arrays as discussed in starting

you can also find the code in my GitHub repository by clicking the link below ⬇⬇⬇

Sorting-Algorithms/MergeSort.java at master · codewithjaspreet/Sorting-Algorithms

⬇ Time & Space Complexity Analysis ⬇

Straight away the space complexity will be O(N) , as we are using an extra array in the merge two sorted arrays part !

Recurrence Relation For Merge Sort :

T(N) = 2T(N/2) + N

Now we can calculate the time complexity of this recurrence relation using any of the substitution , tree method etc.

Recursive Tree Method Calculating the time complexity

hence , the time complexity comes out to be O(N log N) !