Lower bound for Merge Sort running time
$c=\frac{1}{2}$ is enough for large enough $n$.

Indeed, there are positive integers $n_1$ and $n_2$ such that 

$$\begin{eqnarray*}
n &amp;\ge&amp; n_1 \implies -\frac{1}{2} &lt; \log_2 \left ( 1 - \frac{1}{n} \right ) \\
n &amp;\ge&amp; n_2 \implies -\frac{1}{2} &lt; -\frac{1}{n} \log_2 (n - 1).
\end{eqnarray*}$$

Rewriting $$cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$$

as 

$$
cn \left [ \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c} \right ],
$$

we have

$$n \ge \max(n_1, n_2) \implies -2 + \frac{1}{c} &lt; \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c}.$$

But $-2 + \frac{1}{c} \ge 0 \iff c \le \frac{1}{2}$.