= 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 satisfies
$$
T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+O(n),\qquad T(0),T(1)=O(1).
$$
Each 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.
Back to article page
