Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 3 / e / Solution

Let $s_j$ be the total length of the two runs in merge $j$. Because destinations are always appended beyond the old endpoint, the exact space consumption isA simple valid bound is $d\le n+n(n-1)=n^2$, using at most $n-1$ merges. The FIFO queue schedule permits the sharper asymptotic boundTo prove the upper bound, group merges into rounds. Mark the old end of the live segment, and finish a round when all runs present at its start have been consumed. If there are $R>1$ such runs, at most $\lceil R/2\rceil$ merges occur. Only the last merge can pair one remaining old run with an already appended run. Consequently at most $\lceil R/2\rceil$ runs remain; coalescence can only reduce this number. Every start-of-round entry is merged once, and entries in the one possible already appended run are merged at most once more. A round writes at most $2n$ entries. After at most $\lceil {\log }_2{R}_0\rceil$ rounds there is one run, giving $d\le n+2n\lceil {\log }_2{R}_0\rceil$ for $R_0\ge 2$.

For a matching family, let $n=2^{h+1}$ and use $2^h$ repetitions of $[0,1]$. Each initial run has length two. Every merged run still starts at zero and ends at one, so adjacent runs never coalesce. In each of the $h$ complete merging levels exactly $n$ entries are written. Henceon this family. For an already sorted input, no merge occurs and $d=n$.