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