= Solution
<Divide-and-conquer algorithms> split a problem into smaller instances of the same kind, solve them recursively, and combine the solutions. A base case handles instances too small to split. For <merge sort>, divide the input into two halves, recursively sort both halves, and merge them by repeatedly taking the smaller current head. Empty and singleton inputs are already sorted.
The <merge algorithm> step preserves sortedness because its chosen head is no larger than either remaining head; it also preserves every input occurrence. These facts and <mathematical induction> on input length prove correctness. Splitting and merging take $\Theta(n)$ time, so
$$
\boxed{T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n)=\Theta(n\log n).}
$$
At each level the subproblem sizes sum to $n$, and there are $\Theta(\log n)$ levels. Part 3(c) supplies an explicit <Haskell> implementation of this construction with a more specialized comparison rule. Standard <array> implementations use $O(n)$ auxiliary storage.
Back to article page
