Proving recursion depth of merge sort
First of all, let me correct the recursion for the running time of merge sort:
$$
T(n) = \begin{cases} T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta(n) &amp; \text{if } n &gt; 1, \\ \Theta(1) &amp; \text{if } n = 1. \end{cases}
$$
The corresponding recursion for depth is:
$$
D(n) = \begin{cases} \max(D(\lfloor n/2 \rfloor), D(\lceil n/2 \rceil)) + 1 &amp; \text{if } n &gt; 1, \\ 0 &amp; \text{if } n = 1. \end{cases}
$$
(The value of $D(1)$ could also be $1$, depending on how you define depth.)

The solution of this recurrence is $D(n) =\lceil \log_2 n \rceil$.

When $n$ is a power of 2, you can calculate the depth of the recursion tree by noticing that the value of $n$ decreases by a factor of 2 at each level. For the general case, the main observation is that the depth is monotone in $n$, using which you can easily conclude $D(n) \leq \lceil \log_2 n \rceil$ by considering the smallest power of 2 which is at least $n$.