Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / c / Solution

Use merge sort on a list of integers:Here mergeSort denotes the standard merge sort implementation: split into two almost equal lists, recursively sort them, and combine them using the merge algorithm. Splitting and merging take linear time, and each recursion level has total input length $n$. There are $\Theta (\log n)$ levels, so the worst-case time complexity is $\Theta (n\log n)$. Equivalently, $T(n)=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+\Theta (n)$.