Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 7 / b

Each merge consumes and copies a total of $n$ elements, so its time complexity is $\Theta (n)$. HenceAt any level of the recursion tree, all active subranges are disjoint and together contain at most $n$ elements. The total work per level is therefore $O(n)$, and halving gives $O(\log n)$ levels. In fact the full run performs $\Theta (n\log n)$ work for $n\ge 2$.

The shared work array holds $n$ elements, and the depth-first recursion has $O(\log n)$ simultaneous activation records with a constant number of scalar variables each. No recursive call allocates a fresh array. ThereforeThe work array is counted in the auxiliary space complexity even though the caller supplies it. If its actual allocated capacity is $M>n$, the reserved storage is $\Theta (M+\log n)$; choosing capacity $n$ gives the stated bound.