Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 2 / c / Solution

Merging two sorted lists consumes one head per comparison and takes $O(n)$ time in their combined length, assuming constant-cost comparisons. Computing the length and splitting also takes $O(n)$ time. The balanced recursion therefore satisfiesEach recursion level has total linear work, and there are $O(\log n)$ levels. Thus merge sort takes $O(n\log n)$ worst-case time. The final map snd adds $O(n)$, preserving the bound. Costs of comparing variable-size keys must be included separately.