In this article we will look into another sorting algorithm called merge sort algorithm. Like quick sort it is also based upon divide and conquer strategy, in which we break problems into many subproblems which are similar to the original problem, then solve each problem recursively and later combine all subproblems into one to create a solution of the original problem. It is preferred over quick sort because it has time complexity of O(n*logn) in the worst case and also it is more efficient and faster than the quick sort algorithm for large datasets.

What is Merge Sort Algorithm [Explained with examples]

Also Read: What is the Quick Sort Algorithm [Explained with examples]

As we discussed , this algorithm uses divide and conquer strategy. It is one of the most efficient and faster sorting algorithms which is widely used and popular. Sorting algorithms means to arrange the elements in a particular order either in increasing or non-increasing. We sort elements because it is easier to locate an element in an ordered list than an unordered list.

In this algorithm we keep dividing the array into equal or almost equal halves and then we keep merging the array in sorted manner. Its algorithm is very similar to the quick sort algorithm as both use the concept of divide and conquer. Let’s discuss more about the working of the merge sort algorithm.

 

Working 

Lets understand the working of the merge sort algorithm with the help of this diagram.

Here we have taken the example of an unsorted array arr = {6,3,9,5,2,8,7,1}.

In merge sort we first divide the array into two sub arrays of n/2 elements each where n is the total number of elements in the array and we go on dividing the array until the subarray contains only one element. Then after dividing , we merge from bottom to top in a sorted manner. Lets understand this point in the following image.

As we can see we are merging the elements in such a way that it is getting sorted.

For example - the element 6 and 3 merged to become a sub-array = {3,6}.

Now you must have understood the basic concept of merge sort. Let's see the pseudocode of the merge sort algorithm and its explanation too.

 

Pseudocode 

mergeSort(Arr,start,end)
if ( start < end )
       mid = ( start+end ) / 2
       mergeSort(Arr,start,mid)
       mergeSort(Arr,mid+1,end)
       Merge(Arr,start,mid,end)

Merge(Arr,start,mid,end)
n1 = mid - start + 1
n2  = end - mid
Let P[1,2,.,n1+1] and Q[1,2,..,n2+1] are two new arrays
For i = 1 to n1
      P[i] = A[start + i - 1]
for j=1 to n2
      Q[ j ] = A[ mid + j ]
P[ n1 + 1 ] = ∞
Q[ n2 + 1 ] = ∞
i = 1
j = 1
for k = start to end
      if P[i] <= Q[i]
             A[k]=P[i]
             i = i + 1
      else A[k] = R[j]
             j = j + 1

 

Pseudocode explanation

As we can see, there are two functions in this algorithm. One is the Merge function and the other is the mergeSort function. Let's first analyze the mergeSort function. In this function we are passing three parameters arr , start and end. Start is the first index of the array and end is the last index of the array.

First we check if the start is less than the end ? In other words, we are checking if the array contains more than one element ? as we know we cannot divide an array further if there is only one element present. So if start is less than end , we go further and find the mid index of the array.

Then the function calls itself but now with different arguments know the arguments are arr, start, mid it means know we are calling the function for the first half of the array and similarly in the next line we call the mergeSort function for the second half of the array.

As these are recursive functions it means they are calling itself repeatedly , so when the first half will come again into the mergeSort function with its parameters arr, start, mid so it will again check whether start is less than end (now it has become mid in this case) or not and again same process will repeat until there is only one element is left.

As the division has been completed , we will now call the merge function which is the important one to understand here. In the merge function we create two new arrays , we put infinity as the last element in both of these arrays and the rest elements are the same which we get from the original array. Then one by one we compare each element of the two new arrays and put it in the original array in a sorted manner. Let's understand this merge function using an example.

Lets see how this merging has been done. Here start = 1 , mid = 2 and end = 4.

First we create two arrays (P and Q)  for which we calculate the number of elements in these arrays as follows:-

n1 =  2 - 1 + 1 = 2
n2 = 4 - 2 = 2

As new array p contains n1 + 1 elements i.e. 3 elements and same as array p , array q contains 3 elements. Now the two for loops are used to copy the same elements from the sub-array which we are merging. And then at the end of each new array we are putting infinity.

As we can see the P and Q with the infinity at the end, in next step we compare each element of P and Q to get the sorted sub array, like 3 is compared with 5 as 3 is smaller it is placed first, then index i is increased and 6 and 5 is compared as 5 is smaller so 5 is placed after 3 in sorted subarray.

Now j is increased and if we compare 6 and 9, 6 is smaller than 9 that is why it is placed after 5 in sorted subarray and when i is increased now it points to infinity and now when 9 is compared with infinity we can understand 9 is smaller than infinity and it will take last place. In this process we can also understand what is the significance of infinity here in this algorithm. This is how the Merge function works.

 

Implementation in C/C++

a) C++ code

Output

 

b) C code

Output

 

Performance 

As we can see we keep dividing the array into two parts until the array contains only one element. This division of the array takes O(logn) time and the merge function takes O(n) time because it takes linear time to merge two array. The recurrence relation of Merge sort Algorithm is :-

T(n) = 2T(n/2) + O(n)

So the total time which Merge Sort Algorithm takes is O(n*logn). The complexity remains the same in all cases.

• Average case complexity : O(n*logn)
• Best case complexity : O(n*logn)
• Worst case complexity : O(n*logn)
• As we used temporary arrays, the space complexity of the Merge sort algorithm is O(n).

 

Advantages 

• It is fast and efficient algorithm
• It is quicker for larger lists
• It is a stable algorithm
• It has a consistent running time

 

Disadvantages 

• It uses extra storage space to store subelements.
• For small lists also, it repeats whole process hence slower for smaller tasks as well in comparison to other sorting algorithms.
• Even if the list is sorted, it goes through all the steps.

 

Conclusion

Merge sort algorithm is based on divide and conquer approach. We keep dividing the element in two sub parts until the sub part contains only one element. Then we merge sub arrays in sorted manner to get our original sorted array back. The time complexity of merge sort algorithm is same in all case which is O(n*logn). The space complexity of the merge sort algorithm is O(n).