# Do different variants of Mergesort have different runtime?

One of my courses introduced the following question:

Given the recurrence relation for mergesort:

$T(n) = 2T(n/2) + n$

How would the following parameter passing strategies influence the relation and running time of the algorithm:

1. A pointer to the array is passed to the sorting function,

2. The entire array is copied to a separate location before applying the sorting function,

3. A subsection of the array is copied to a separate location before applying the sorting function on that subsection.

For 1., since this is how mergesort is used most of the time, we can solve it easily using the master theorem.

$f(n) = \Theta(n^{\log_b a}) = \Theta(n) \implies T(n) = \Theta(n \log n)$

For 2. however, I am a bit baffled. Although we do an additional work of $O(n)$, we are only doing so once at the beginning of the sort. Hence, doing one additional instance of $O(n)$ work should not influence the order of the running time (because it already is of a larger order). Hence, for both 2. and 3. the running time would remain at $T(n) = \Theta(n \log n)$.

Is this reasoning valid? Something tells me that the $O(n)$ copying should have more of an impact, but I can't seem to give myself a good enough reason that it should be responsible to slow it down enough so that it would worse (i.e. $O(n^2)$).

Any thoughts or hints would be quite appreciated!

• 2. Probably means that each time mergesort is called recursively the entire array is copied somewhere. – George Sep 12 '13 at 8:09

2. Copying the entire array once adds a linear term globally, so the recurrence does not change. If you are only after $\Theta$-behaviour, ignore it (since the actual algorithm dominates).
3. Now this adds linear overhead to every call of the routine, changing the recurrence from $\ldots + n$ to something like $\ldots + 2n$. Of course, this results only in a different constant so the result is again not influenced (see Master Theorem).