Time Complexity and Space Analysis of Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm. It divides the array into smaller subarrays, sorts them, and then merges the sorted subarrays.

Let:

• T(n) = time taken to sort n elements.
• c * n = time taken to merge n elements, where c is a constant.

Merge Sort performs three main steps:

• It divides the array into two halves, each containing n/2 elements.
• It recursively sorts both halves. Sorting each half takes T(n/2) time, so sorting both halves takes 2 * T(n/2) time.
• It merges the two sorted halves. Merging n elements takes linear time, represented by c * n.

Therefore, the recurrence relation is: T(n) = 2 * T(n/2) + c * n

Expanding the recurrence:

• T(n) = 2 * [2 * T(n/4) + c * n/2] + c * n
• T(n) = 4 * T(n/4) + 2 * c * n

After expanding for k levels: T(n) = 2^k * T(n/2^k) + k * c* n

• The division stops when each subarray contains one element: n/2^k = 1.
• Therefore: n = 2^k
• Taking log₂ on both sides: k = log₂ n
• Substituting this value: T(n) = n * T(1) + log₂ n * c * n
• Since T(1) and c are constants: T(n) = O(n) + O(n log n) = O(n log n)

Therefore, the time complexity of Merge Sort is:

O(n log n)

Best, Average and Worst Case Time Complexity

Merge Sort has the same time complexity in all cases because it always divides the array into smaller halves and merges the resulting subarrays.

• The array is divided into halves until each subarray contains one element, creating O(log n) levels.
• At each level, all n elements are processed during merging, which takes O(n) time.

Thus, the time complexity is:

Auxiliary Space Analysis of Merge Sort

Merge Sort uses extra space for the temporary arrays required during the merging process.

• The temporary array can store up to n elements, requiring O(n) space.
• The recursive calls create a recursion stack with a maximum depth of O(log n).

Therefore, total auxiliary space is: O(n) + O(log n)

Since O(n) dominates O(log n), the auxiliary space complexity of Merge Sort is:

O(n)