Algorithms: Design and Analysis, Part 1 - Exam Question 3

Problem:

What is the asymptotic worst-case running time of MergeSort, as a function of the input array length $n$?

Solution:

Actually all recursion levels will take $\theta(n)$ time to create the merged arrays, so the time is obviously $\theta(n \log n)$ time.