Understanding Recurrence Relation of Merge Sort
1. Divide-and-Conquer Approach
The divide-and-conquer strategy is a common technique for designing efficient
algorithms. It involves three main steps:
1. Divide: Break the problem into smaller subproblems of the same type.
2. Conquer: Solve the subproblems recursively. If the subproblems are small
enough, solve them directly.
3. Combine: Merge or combine the solutions of the subproblems to get the solution
to the original problem.
2. Merge Sort Algorithm
Merge sort uses the divide-and-conquer strategy to sort an array. Here's how it
works:
Steps in Merge Sort
1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half using merge sort.
3. Combine: Merge the two sorted halves into a single sorted array.
3. Pseudocode for Merge Sort
Merge Sort:
MERGE-SORT(A, p, r)
1. if p < r:
2. q = ⌊(p + r) / 2⌋ # Middle point
3. MERGE-SORT(A, p, q) # Sort the left half
4. MERGE-SORT(A, q + 1, r) # Sort the right half
5. MERGE(A, p, q, r) # Merge the two halves
Merge Operation:
MERGE(A, p, q, r)
1. Let n1 = q - p + 1
2. Let n2 = r - q
3. Create arrays L[1..n1+1] and R[1..n2+1]
4. Copy A[p..q] to L[1..n1] and A[q+1..r] to R[1..n2]
5. Add "sentinel" values (∞) to the ends of L and R
6. i = 1, j = 1
7. for k = p to r:
if L[i] <= R[j]:
A[k] = L[i]
i=i+1
else:
A[k] = R[j]
j=j+1
4. Recurrence Relation for Merge Sort
The total time taken by merge sort for an input of size n, denoted as T(n), can be
expressed as:
T(n) =
O(1), if n = 1 (base case)
2T(n/2) + O(n), if n > 1 (recursive case)
Explanation:
1. Base Case (n = 1): If the array has only one element, it is already sorted, so the
time taken is O(1).
2. Recursive Case (n > 1): The array is divided into two halves, each of size n/2.
Sorting these halves takes 2T(n/2), as we recursively call merge sort twice.
Combining (merging) the two sorted halves takes O(n), since we linearly compare
and merge all n elements.
5. Solving the Recurrence
Let’s solve the recurrence step by step to derive the overall time complexity:
Step 1: Expand the Recurrence
T(n) = 2T(n/2) + cn
T(n) = 2[2T(n/4) + c(n/2)] + cn
T(n) = 4T(n/4) + 2cn/2 + cn
T(n) = 8T(n/8) + 4cn/4 + 2cn/2 + cn
Step 2: Generalize the Pattern
After k levels of expansion, the pattern becomes:
T(n) = 2^k T(n/2^k) + kcn
Step 3: Stop the Recursion
The recursion stops when the subproblem size becomes 1:
n / 2^k = 1 → k = log2 n
Step 4: Simplify
T(n) = n * O(1) + cn log2 n
Ignoring constants and lower-order terms, the total time complexity is:
T(n) = O(n log n)
