What is the time complexity of Mergesort?

What is the time complexity of Mergesort?

Approach: Analyze the divide-and-conquer recurrence.

O(n log n) in all cases (best, average, worst). The array is recursively split in half (log n levels) and merged back together (n work per level).

Follow-up: Is Mergesort in-place?

Key concepts: O(n log n), divide and conquer, stable sorting.