 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.