What is the time complexity of a merge sort algorithm?

Merge Sort is a popular, efficient, comparison-based sorting algorithm that follows the divide and conquer paradigm. Understanding its time complexity is fundamental for assessing its performance characteristics in various applications.

How Merge Sort Works

Merge Sort operates by recursively dividing an unsorted list into n sublists, each containing one element (a list of one element is considered sorted). It then repeatedly merges these sublists to produce new sorted sublists until there is only one sorted list remaining.

Time Complexity Analysis

The time complexity of Merge Sort is derived from its three main steps:

• Divide: This step involves finding the middle point of the array and splitting it into two halves. This operation takes constant time, O(1).
• Conquer: This step recursively sorts the two sub-arrays. If the original array has size 'n', each sub-array will have size 'n/2'. The time taken for this step is 2T(n/2).
• Combine: This step merges the two sorted sub-arrays back into a single sorted array. The merging process requires comparing and placing elements from both sub-arrays, taking linear time proportional to the total number of elements being merged, which is O(n).

Combining these steps, the recurrence relation for the time complexity T(n) of Merge Sort is:

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

Solving this recurrence relation using the Master Theorem or the substitution method yields a time complexity of O(n log n).

Best, Average, and Worst Case

A notable advantage of Merge Sort is its consistent performance across different input arrangements. The division and merging operations always involve iterating through all elements, regardless of whether the array is nearly sorted, reverse-sorted, or randomly ordered. Therefore, the time complexity remains O(n log n) for the best, average, and worst-case scenarios.

Space Complexity

Merge Sort typically requires O(n) auxiliary space. This is primarily due to the temporary array created during the merging step to hold the combined sorted elements. While some in-place merge sort variants exist, they often come with increased complexity or a higher constant factor for time.

Summary

• Time Complexity: O(n log n) in all cases (best, average, and worst).
• Space Complexity: O(n) auxiliary space (not in-place).