= Solution
Sequential accumulation writes merged outputs of lengths $2n,3n,\ldots,kn$. Its total work is
$$
\Theta\!\left(n\sum_{j=2}^{k}j\right)=\boxed{\Theta(nk^2)}\quad(k\geq2).
$$
The growing <list prefix> is repeatedly copied, even though its internal order is already known.
Instead, divide the family of <arrays> into two nearly equal halves, recursively merge each half, and merge the two resulting <sorted arrays>. A balanced merge tree has $\lceil\log_2 k\rceil$ levels; at each level at most $kn$ entries are read or written in merges. Thus the bound is \b[$\Theta(kn\log k)$ for $k\geq2$], including the output work. Equivalently the recurrence in the number of <arrays> is $M(k)=M(\lfloor k/2\rfloor)+M(\lceil k/2\rceil)+\Theta(kn)$. The one-<array> case simply returns it, or costs $\Theta(n)$ if a fresh output <array> is required.
Back to article page
