# Applying the Master Theorem on Merge sort

I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into calls which aren't natural numbers, but how do I present this argument formally?

The proof:

The recursion splits the problem into two sub problems, each with at most $\lceil \frac{n}{2} \rceil$ elements. Therefore, we can apply the Master Theorem with $a = b = 2$. So, $\log_b{a}$ = 1. The cost of splitting is $0$ comparisons, and that of combining is at most $n−1$ comparisons. Hence the cost of split/combine is $\Theta(n) = \Theta(n\log_b{a})$, so we are in the second case of the Master Theorem, and therefore the total cost is $\Theta(n\log n)$.

• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Aug 9 '16 at 13:38

You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you can split it into two arrays of length at most 2.5. But you are able to split it into two arrays of length at most $\lceil 2.5 \rceil = 3$.
Note that the textbook estimates the time it takes to sort an array with at most $n$ elements (rather than the time it takes to sort an array with exactly $n$ elements).