Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 5 / b / Solution

Sequential accumulation writes merged outputs of lengths $2n,3n,\dots ,kn$. Its total work isThe 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 $\Theta (kn\log k)$ for $k\ge 2$, 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.