Exact Analysis of the Merge Sort
Let us consider the recurrence
$$
T(n) =
\begin{cases}
1 &amp; \text{if } n = 1, \\
T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n &amp; \text{if } n \geq 2.
\end{cases}
$$
Using OEIS (A033156), we find that the exact solution to this recurrence is
$$
T(n) = n(\lfloor \log_2 n \rfloor + 3) - 2^{\lfloor \log_2 n \rfloor + 1}.
$$
Curiously, OEIS presents a different recurrence relation with the same solution:
$$
T(n) =
\begin{cases}
1 &amp; \text{if } n = 1, \\
T(n-1) + \lfloor T(n-1)/(n-1) \rfloor + 2 &amp; \text{if } n \geq 2.
\end{cases}
$$
The OEIS entry contains references to articles analyzing the recurrence in the context of divide-and-conquer, which you might find helpful if you want to analyze similar such recurrences.