= 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. Thus
$$
\boxed{T_{\rm merge}(m,n)=O(m+n),\quad\text{with worst case }\Theta(m+n).}
$$
An 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> satisfies
$$
T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n),\qquad T(0),T(1)=\Theta(1).
$$
At 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. Consequently
$$
\boxed{T_{\rm mergesort}(n)=\Theta(n\log n)\quad(n\ge2).}
$$
The 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.
Back to article page
