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

Assume head comparison and construction of one list cell take constant time. In the merge algorithm, every comparison removes one head from the recursive inputs, and evaluation stops as soon as either is empty. For lengths $m,n>0$, at most $m+n-1$ comparisons and the same number of newly constructed cells are required; the untouched suffix is shared. Inputs which keep both lists nonempty until the last comparison attain this bound. ThusAn initially empty input makes this particular implementation constant-time; not every pair requires linear work.

The balanced merge sort spends $\Theta (n)$ time per call on list length, splitting and merging. Hence its time complexity satisfiesAt each recursion level the lengths of its disjoint subproblems sum to $n$, so the work per level is $\Theta (n)$, and balanced splitting gives $\Theta (\log n)$ levels. ConsequentlyThe length and splitting traversals change the constant factor, not this asymptotic order; repeatedly inserting elements into a sorted list would not give the same complexity.