Mergesort Time Complexity Analysis
You'll learn: How to derive Mergesort's O(n log n) time complexity using recurrence relations and recursion tree analysis.
The Core Idea
Mergesort splits an array in half recursively until reaching single elements, then merges them back together. To understand why this takes O(n log n) time, we analyze two aspects: how many levels of recursion occur and how much work happens at each level.
Recurrence Relation Approach
Let T(n) represent the time to sort n elements:
- Dividing: O(1) — just finding the midpoint
- Two recursive calls: 2 × T(n/2) — sorting each half
- Merging: O(n) — combining sorted halves
This gives us: T(n) = 2T(n/2) + O(n)
With base case T(1) = O(1).
Recursion Tree Analysis
Picture the recursion as a tree:
- Root level: Merge n elements → O(n) work
- Next level: Merge two groups of n/2 → 2 × O(n/2) = O(n) work
- Next level: Merge four groups of n/4 → 4 × O(n/4) = O(n) work
Notice that each level does O(n) total work, no matter how many subproblems exist.
How many levels? Starting with n elements, we divide by 2 each time until reaching size 1. This takes log₂(n) levels (like how 8 → 4 → 2 → 1 takes 3 steps, and log₂(8) = 3).
Putting It Together
- Work per level: O(n)
- Number of levels: log n
- Total time: O(n) × log n = O(n log n)
This holds for best, average, and worst cases because Mergesort always divides evenly and always merges completely.
Key Takeaway: Mergesort achieves O(n log n) time complexity because it performs O(n) work across log n levels of recursion, making it dramatically faster than O(n²) elementary sorts for large datasets.