 Solution

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.