Many students struggle to visualise what exactly makes the worst case of merge sort happen. Unlike Quicksort, where a sorted array is a nightmare, Merge Sort finds its “worst” scenario in a very specific, staggered permutation. To understand Data Structures and Algorithms (DSA), you need to know how to make this permutation. This article will explain how these permutations work and how they affect the algorithm.
Also Read – Advance Data Structure and Algorithms
What is the Worst Case of Merge Sort?
To understand how the worst scenario happens, it’s helpful to look at the algorithm’s basic parts:
- The Divide Phase: The algorithm keeps splitting the array in half until each subarray has only one element.
- The Merge Phase: After splitting the data, the algorithm starts putting it back together by comparing the smallest elements from two sorted subarrays.
- Selection Logic: When two elements are compared, the smaller one is chosen and added to the sorted main array.
- Comparison Efficiency: The amount of comparisons made determines how well it works. In the best situation, one subarray runs out of space soon, and the other elements can be relocated without any more comparisons.
- Worst-Case Strategy: It occurs when we delay the exhaustion of either subarray for as long as possible, forcing the algorithm to perform a comparison for almost every single element.
It is mathematically defined as O(N log N). While this looks the same as the best and average cases, the constant factor changes based on the number of comparisons.
A “worst-case” permutation is one that forces the algorithm to perform the maximum possible number of comparisons at every level of recursion. This happens when the elements are distributed such that in every merge step, we have to compare elements until only one element is left in one of the subarrays.
Specifically, it happens when:
- The left and right subarrays have elements that are “interleaved.”
- The largest element of one subarray is smaller than the largest element of the other, but larger than the second-to-last element of the other.
- Every comparison results in an element being picked from alternating sides until the very last possible moment.
Also Read – Introduction to Red-Black Tree
Worst Case of Merge Sort Permutation Construction
Generating an example requires a recursive approach. We want to take a sorted array and “un-merge” it into a state that would require maximum comparisons to put back together.
How to Build Merge Sort Worst Case Permutation
- Start with a sorted array of N elements.
- To create the worst case, we need to split this sorted array into two sequences such that all elements at even positions (0, 2, 4…) go to one subarray and all elements at odd positions (1, 3, 5…) go to the other.
- Recursively apply this “even-odd” split to the resulting subarrays until you reach a subarray size of 1.
- Join these elements back in the order they were split.
Worst Case of Merge Sort Example
N = 4
Let’s look at a sorted array: {1, 2, 3, 4}.
- Step 1: Split the indices into even and odd ones.
- Left (Even numbers 0 and 2): {1, 3}
- Right (Odd indices 1 and 3): {2, 4}
- Step 2: The new order is {1, 3, 2, 4}.
When you execute the merge sort algorithm on {1, 3, 2, 4}, the last step will compare 1 and 2, then 3 and 2, and finally 3 and 4. This makes sure that the most comparisons are made.
N = 8
Let’s look at a bigger sample to better comprehend the pattern.
Array that has been sorted:
{1, 2, 3, 4, 5, 6, 7, 8}
Step 1: Separate the numbers into even and odd:
Left: {1, 3, 5, 7}
Right: {2, 4, 6, 8}
Step 2: Use the same logic over and over again:
→ {1, 5, 3, 7} on the left
Right → {2, 6, 4, 8}
Step 3: The last change:
{1, 5, 3, 7, 2, 6, 4, 8} This order makes sure that elements are compared in an alternating pattern throughout every merge step, which forces the most comparisons.
Worst Case of Merge Sort Time Complexity
“What is the worst case complexity of merge sort?” is a question that comes up a lot in interviews.
The answer is O(N log N).
The recurrence relation for Merge Sort is:
T(n) = 2T(n/2) + θ(n)
The height of the recursion tree stays log N even in the worst-case scenario because the array is always split in half. At each level, the “merge” process requires O(n) time.Therefore, the overall time complexity remains logarithmic-linear. However, the number of comparisons in the worst case is exactly N log2 N – N + 1.
Also Read – Geometric Algorithms
Comparison Count in Merge Sort
In the worst case, the number of comparisons is maximised at every merge step.
For N elements, the total comparisons are approximately:
N log₂N – N + 1
Example:
For N = 8
Comparisons ≈ 8 × log₂(8) – 8 + 1
= 8 × 3 – 8 + 1
= 17 comparisons
This is higher than best-case scenarios, where fewer comparisons are needed because one subarray gets exhausted early.
Worst Case of Merge Sort Algorithm
The process to construct the worst case permutation can be written in a structured way:
Algorithm:
- If the array size is 1, return the array.
- Create two empty arrays: left and right.
- Traverse the array:
- Put elements at even indices into the left array
- Put elements at odd indices into the right array
- Recursively apply the same function to left and right.
- Concatenate left and right arrays.
- Return the result.
This algorithm ensures that at every level, the elements are arranged to maximise comparisons during merging.
Python Code for Worst Case of Merge Sort
Here is a simple implementation of the above logic in Python:
def worst_case_merge(arr):
if len(arr) <= 1:
return arr
left = arr[::2] # even index elements
right = arr[1::2] # odd index elements
left = worst_case_merge(left)
right = worst_case_merge(right)
return left + right
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8]
result = worst_case_merge(arr)
print(result)
Output:
[1, 5, 3, 7, 2, 6, 4, 8]
This program rearranges a sorted array into a worst-case permutation for merge sort.
Steps to Find Worst Case of Merge Sort
If you are asked to write a program to find this permutation, you can follow this structured approach:
- Create two empty arrays: One for the left half and one for the right half.
- Distribute elements: For a sorted input, put elements at indices 0, 2, 4… into the left array and indices 1, 3, 5… into the right array.
- Recursive Call: Pass the left array into the function again to further scramble it. Pass the right array similarly.
- Base Case: If the array size is 1 or 2, the current order is sufficient to return.
This “top-down” scrambling ensures that at every single level of the merge sort algorithm, the elements are perfectly misaligned to cause maximum work for the processor.
Importance of Merge Sort for Developers
It’s not simply an intellectual exercise to know the worst case for merge sort. It tells you about:
- Cache Efficiency: The complexity is O(N log N), although in the worst case, the way elements are accessed can cause more cache misses.
- How strong is the algorithm? Because Merge Sort is stable even in the worst situation, it is the best choice for external sorting (sorting data that doesn’t fit in RAM).
- Counting Comparisons: In competitive programming, you could be asked to determine the least or most comparisons that can be made for a certain N.
Merge Sort is a lot more reliable than Quicksort, but knowing how to activate its most “expensive” path can help you build better test cases and grasp the limits of divide-and-conquer tactics.
FAQs
What is the worst case complexity of merge sort?
It is O(N log N). This remains consistent across best, average, and worst scenarios because the array is always divided into two equal halves.
When does the merge sort worst case occur?
It occurs when the input array is arranged such that every merge operation requires the maximum number of comparisons. This happens when elements are interleaved across the two subarrays being merged.
How is the merge sort worst case different from Quicksort?
When you use Quicksort, the worst situation (O(N²)) comes when the arrays are already sorted or sorted in reverse order. The worst case for the merge sort algorithm still takes O(N log N) time, but it needs a certain "scrambled" permutation to make the most comparisons.
Can you give an example?
If the array has 4 elements long, the sorted version is {1, 2, 3, 4}. For example, {1, 3, 2, 4} makes the most comparisons during the merging step.
Is the time complexity better than bubble sort?
Yes, a lot. Bubble sort takes O(N²) time, while this one takes O(N log N) time. Merge sort will always be better than bubble sort for big datasets, no matter how the input is arranged.