I was wondering to myself what the actual run time of Mergesort was, so I thought like this:
We have the sort operation that takes time $s(2) = 1$ and $s(1) = 0$. Merging two sorted sequences with length $k$ and $l$ takes $m(k, l) = k+l$ time. If we want to sort a sequence with $n$ elements we can also sort the sequences with index $\left[0, n/2\right>$ and $\left[n/2, n\right>$ with added cost $m(n/2,n/2) = n$.
We already know $s(2) = 1$. Now we also know that $s(n) = 2 \cdot s(n/2) + n$. In other words: $2(n + 2(n/2 + \dots 2(2 + s(2))) = s(n)$. If I reverse that I see that $s(2n) = 2(n + s(n))$.
I note that if we have a sequence with $2^k$ elements we can divide this sequence and subsequences in two $\log_2(2^k) - 1 = k-1$ times to get sequences of length 2.
Now that's where I'm stuck. I have no idea how to expand $s(2n) = 2(n + s(n))$. Can someone give me a push in the right direction?
Please be gentle, I'm only known with high-school math.