When Will the Worst Case of Merge Sort Occur?

1. Overview

Merge Sort is one of the most popular sorting algorithms where we divide a problem into subproblems. When the solution to each subproblem is ready, we ‘merge’ the results from the subproblems to solve the main problem.

In this tutorial, we’ll discuss the time complexity (a.k.a. Big O) of Merge Sort and also the combination that causes the worst case.

2. Two Steps of Merge Sort

The algorithm has two steps.

Step 1 is “Divide”, where the algorithm repeatedly divides the array into two halves until we reach a stage where the size of the subarray is 1:

Merge Sort Algorithm v3

The time complexity of division function of array above (having 16 elements and = 16) is 8+4+2+1 = 15. In other words, when the size of the array is $\mathbf{n}$ , the time complexity of the divide function of Merge Sort is ( $\mathbf{n}$ /2+ $\mathbf{n}$ /4 …till 1) which is also $\mathbf{O(n)}$ .

Step 2 of the algorithm includes “Merge + Sort”, where two subarrays are merged so that a sorted array is created from each pair of subarrays. In the last step, the two halves of the original array are merged so that the complete array is sorted:

Merge Sort Algorithm v4

This algorithm loops through log(n)-1 times and the time complexity of every loop is O(n) , so the time complexity of the entire function is $O(n \times (log(n)))$ .

The complexity of the entire algorithm is the sum of the complexity of two steps which is $\mathbf{O(n \times logn)}$ . This happens to be the worst case of Merge Sort as well.

3. The Worst Case of Time Complexity for Merge Sort

Time complexity can be improved if the number of comparisons can be reduced while doing merge and sort. However, no optimization is possible if the left and right sub-arrays involved in the merge operation have alternate elements of the sorted array. For example, if the left and right sub-array are {1,3,5,7} and {2,4,6,8} respectively, then every element for both arrays needs to be compared at least once, which will result in the worst time complexity.

The process flow of the algorithm will look below:

Worst Case Merge Sort 1

If we use this algorithm on array {1,2,3,4,5,6,7,8}, we’ll find {5,1,7,3,6,2,8,4} as the combination that’ll produce worst complexity for merge sort as shown below:

Worst case of merge sort example

4. Conclusion

In this article, we discussed the worst time complexity of Merge Sort, which is $O(n \times logn)$ . It occurs when the left and right sub-arrays in all merge operations have alternate elements.

Persistence

REST

Security

1. Overview

2. Two Steps of Merge Sort

3. The Worst Case of Time Complexity for Merge Sort

4. Conclusion