= Solution
Each merge consumes and copies a total of $n$ elements, so its <time complexity> is $\Theta(n)$. Hence
$$
T(1)=\Theta(1),\qquad
T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n).
$$
At 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\geq2$.
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>. Therefore
$$
\boxed{\text{time }\Theta(n\log n),\qquad
\text{auxiliary space }\Theta(n)+O(\log n)=\Theta(n).}
$$
The 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.
Back to article page
