Analyzing the Recursive Version

Let’s analyze the recursive merge sort the same way we analyzed the bottom-up one: time first, then space.

Time

Here is a diagram of the work recursive merge sort does. Each row is a level of the recursion: the top is the whole array, and each level below splits every subarray in half, down to single elements.

level 0:            [ . . . . . . . . ]        one piece  of size n
level 1:        [ . . . . ]   [ . . . . ]      two pieces of size n/2
level 2:      [ . . ] [ . . ] [ . . ] [ . . ]  four pieces of size n/4
   ...
last level:   [.] [.] [.] [.] [.] [.] [.] [.]  n pieces of size 1

Now think about the merging work that happens on the way up, one level at a time. The merges at a single level work on subarrays that do not overlap, and together those subarrays cover the whole array, so all the merges at one level together cost $O(n)$. That is the same observation we made for the bottom-up version, where each pass cost $O(n)$. A level of the recursion corresponds to a pass.

How many levels are there? We start at size $n$ and halve until we reach size $1$. Halving $n$ down to $1$ takes ${\log }_{2}n$ steps, so there are about ${\log }_{2}n$ levels. We have seen this in binary search too.

That is $O(n)$ work per level times $O(\log n)$ levels, so the running time is $O(n\log n)$, the same as the bottom-up version.

Space

As before, we split this into input space and auxiliary space.

The input space is $O(n)$: the array we are sorting.

There are two things to count in the auxiliary space now.

The first is the same as before: the temporary array that merge creates. The merges still run one at a time, because merge is only called after the recursive calls return, and it finishes before the next merge begins. So this part is still $O(n)$.

The second is new: the call stack. When we studied space complexity, we saw that a recursive method’s stack frames count toward its space, and that the cost depends on the maximum depth of the call stack. So we need the maximum depth here. The recursion goes down one level at a time, so at most about ${\log }_{2}n$ frames are on the stack at once. That part is $O(\log n)$.

Adding them up, the auxiliary space is $O(n)+O(\log n)$. The $O(n)$ term dominates, so the auxiliary space is $O(n)$, and the total space is $O(n)$ as well. That is asymptotically the same as the bottom-up version.

In practice, the call stack has a fixed size limit, and a recursive method whose recursion depth is much larger than ${\log }_{2}n$ can reach that limit.