# How to continue this argument/proof?

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.

-

Since mergesort has $n\log n$ complexity (which you can learn from Wikipedia in case you don't already know it), a reasonable guess for $s(n)$ would be $s(n)=\alpha n\log n$. Also, note that adding a multiple of $n$ to a solution yields another solution, so we can use the ansatz $s(n)=\alpha n\log n+\beta n$. Substituting this into your recurrence yields

$$\alpha2n\log(2n)+\beta2n=2(n+\alpha n\log n+\beta n)\;,$$

$$\alpha2n(\log2+\log n)=2n+2\alpha n\log n\;,$$

$$\alpha2n\log2=2n\;,$$

$$\alpha\log2=1\;,$$

$$\alpha=\frac1{\log2}\;,$$

so $s(n)=n\log n/\log 2+\beta n=n\log_2n+\beta n$.

Then substituting the initial value $s(2)=1$ yields $s(2)=2\log_22+2\beta=2+2\beta=1$ and $\beta=-\frac12$ and finally $s(n)=n\log_2n-\frac12n$. Note that your other initial value is inconsistent with the recurrence; I'm not sure how you arrived at these initial values, but if that's what you want, you'll have to treat $s(1)=0$ as a special case.

-
I don't think that assuming mergesort has $n \log n$ complexity because Wikipedia says so is correct for a mathematical argument. Also, $s(1) = 0$ because a sequence of 1 is already sorted and $s(2) = 1$ because 2 elements can be sorted using one comparison (or one time). –  orlp Nov 8 '11 at 22:18
@nightcracker: That's a misunderstanding. I didn't assume it, I just used it as an ansatz to find the solution. Once the solution is found, you can check it rigorously without recourse to Wikipedia. Concerning the initial values: You can do it that way, but then you're not solving the $n=2$ case by recursion, so there's no reason to expect the recurrence to hold for that case, so then $s(1)=0$ is a special case disjoint from the others. –  joriki Nov 8 '11 at 22:58