If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our **Contribution Guidelines**.

# When Will the Worst Case of Merge Sort Occur?

Last modified: October 13, 2021

**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:**

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 , **the time complexity of the divide function of Merge Sort is (/2+/4 …till 1) which is also **.

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:

This algorithm loops through times and the time complexity of every loop is , so the **time complexity of the entire function** is .

The complexity of the **entire algorithm is the sum of the complexity of two steps** **which is .** 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:

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:

## 4. Conclusion

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