Analyze mathematically the number of compares that mergesort makes to sort an array of length \(n\). For simplicity, assume \(n\) is a power of 2. which is similar to, but more complicated than, the recurrence that we considered for binary search. But if we divide both sides by \(2^{n}\), we get \[M\left(2^{k}ight) / 2^{k} \leq M\left(2^{k-1}ight) / 2^{k-1}+1\] which is precisely the recurrence that we had for binary search. That is, \(M\left(2^{k}ight) / 2^{k} \leq\) \(T\left(2^{k}ight)=n\). Substituting back \(n\) for \(2^{k}\) (and \(\lg n\) for \(k\) ) gives the result \(M(n) \leq n \lg n\). A similar argument shows that \(M(n) \geq 1 / 2 n \lg n\).