What is the ​​Time Complexity of Merge Sort?

Merge sort is a sorting algorithm that is trivial to apply and has a time complexity of $O(n * logn)$ for all conditions (best case, worst case and average case). This algorithm is based on the divide and conquers strategy.

The sorting algorithm continuously splits a list into multiple sublists until each sublist has only one item left. It then merges those sublists into a sorted list.

What is Merge Sort?

Merge Sort, considered to be the most efficient sorting algorithm, works on the principle ‘Divide and Conquer‘.

The algorithm can be divided into three parts :

1. Divide – It is the initial stage where the midpoint of the array is found using $mid=start+(end-start)/2$
2. Conquer – In this step, the array is divided into subarrays, using the midpoint calculated. The process repeats itself recursively until all elements become single array elements.
3. Combine – In this step, the subarrays formed are combined in sorted order.

Example :

Sorting the array [45, 22, 67, 14, 55, 38] using merge sort.

Complexity Analysis of Merge Sort

Merge sort repeatedly divides the array into two equally sized parts.

Thus merge sort time complexity depends on the number of division stages.

The number of division stages is $log~2~n$.

On each merge stage, n elements are merged.

• Step 1 – $n × 1$
• Step 2 – $n/2 × 2$
• Step 3 – $n/4 × 4$

Merge Sort time complexity is calculated using time per division stage. Since the merge process has linear time complexity, for n elements there will be $n * log~2~n$ division and merge stages.

Hence, regardless of the arrangement, the time complexity of Merge Sort is $O(nlogn)$

Analysis of Merge Sort Time Complexity

Best Case Time Complexity of Merge Sort

The best case scenario occurs when the elements are already sorted in ascending order.
If two sorted arrays of size n need to be merged, the minimum number of comparisons will be n. This happens when all elements of the first array are less than the elements of the second array.
The best case time complexity of merge sort is $O(n*logn)$.

Average Case Time Complexity of Merge Sort

The average case scenario occurs when the elements are jumbled (neither in ascending nor descending order). This depends on the number of comparisons.
The average case time complexity of merge sort is $O(n*logn)$.

Worst Case Time Complexity of Merge Sort

The worst-case scenario occurs when the given array is sorted in descending order leading to the maximum number of comparisons.
In this case, for two sorted arrays of size n, the minimum number of comparisons will be 2n.
The worst-case time complexity of merge sort is $O(n*logn)$.

Analysis of Merge Sort Space Complexity

In merge sort, all elements are copied into an auxiliary array of size N, where N is the number of elements present in the unsorted array.
Hence, the space complexity for Merge Sort is $O(N)$.

Learn more

• Merge Sort

Conclusion

• Merge sort is a reliable sorting algorithm that uses a ‘divide and conquers‘ paradigm.
• Initially, it divides the problem into sub-problems and solves them individually.
• Then, it combines the results of sub-problems to get the solution to the original problem.
• Merge sort is a recursive sorting algorithm.
• The recurrence relation of merge sort is $T(n) = 2T(n/2) + θ(n)$.
• The time complexity of merge sort is
  • Best Case: $O(n*logn)$
  • Average Case: $O(n*logn)$
  • Worst Case: $O(n*logn)$
• The space complexity of merge sort is $O(n)$.