Number of comparisons in mergesort:

$$\begin{aligned} C_N &= C_{\lfloor N/2 \rfloor} + C_{\lceil N/2 \rceil} + N & \text{ for } N > 1 \text{ with } C_1 = 0 \\ \end{aligned}$$

How do we solve for $C_N$ ?

$$\begin{aligned} C_{N+1} &= C_{\lfloor (N+1)/2 \rfloor} + C_{\lceil (N+1)/2 \rceil} + N + 1 \\ &= C_{\lceil N/2 \rceil} + C_{\lfloor N/2 \rfloor + 1} + N + 1 & \text{!}\\ C_{N+1} - C_N &= C_{\lfloor N/2 \rfloor + 1} - C_{\lfloor N/2 \rfloor} + 1 \\ \end{aligned}$$

Now, let

$$\begin{aligned} D_N &= C_{N+1} - C_N \\ &= C_{\lfloor N/2 \rfloor + 1} - C_{\lfloor N/2 \rfloor} + 1 \\ \therefore D_N &= D_{\lfloor N/2 \rfloor} + 1 \\ \end{aligned}$$

Note

$$\begin{aligned} D_1 &= C_{1+1} - C_1 = C_2 - C_1 = C_2 \\ C_2 &= C_{\lfloor 2/2 \rfloor} + C_{\lceil 2/2 \rceil} + 2 \\ &= C_1 + C_1 + 2 = 2 \\ \therefore D_1 &= 2 \\ D_N &= D_{\lfloor N/2 \rfloor} + 1 \\ &= D_1 + \lfloor \ln N \rfloor & \text{telescope} \\ \therefore D_N &= \lfloor \ln N \rfloor + 2 \\ \end{aligned}$$

Solving for $C_N$,

$$\begin{aligned} C_{N+1} &= C_N + D_N & \text{rearranging terms} \\ &= C_N + \lfloor \ln N \rfloor + 2\\ &= C_1 + (\lfloor \ln 1 \rfloor + 2) + \cdots + (\lfloor \ln N \rfloor + 2) & \text{telescope} \\ &= 2N + C_1 + \sum_{k=1}^N \lfloor \ln k \rfloor \\ &= 2N + \sum_{k=1}^N \lfloor \ln k \rfloor \\ C_N &= 2(N-1) + \sum_{k=1}^{N-1} \lfloor \ln k \rfloor \\ &= (N-1) + \sum_{k=1}^{N-1} \big(\lfloor \ln k \rfloor + 1\big) \\ C_N &= N - 1 + \sum_{k=1}^{N-1} \big(\lfloor \ln k \rfloor + 1\big) \\ \end{aligned}$$

Note $\lfloor \ln k \rfloor + 1$ is the number if bits in the binary representation of k. Here is why.

• Let $B_N$ be the number if bits in the binary representation of $N$.
• Obviously, $B_1 = 1$.
• removing the right most bit of $N$ gives $\lfloor N/2 \rfloor$.

Therefore $B_N = B_{\lfloor N/2 \rfloor} + 1$ is the number of bits in the binary representation of N, for $N > 1$ with $B_1 = 1$. Interestingly, this happens to be the same recurrence as binary search. Now

$$\begin{aligned} B_N &= B_{\lfloor N/2 \rfloor} + 1 \\ &= B_1 + \lfloor \ln N \rfloor & \text{telescope} \\ \therefore B_N &= \lfloor \ln N \rfloor + 1 \\ \end{aligned}$$

Thus the theorem:

$$\begin{aligned} C_N = N −1 + \text{ number of bits in binary representation of all numbers} < N. \end{aligned}$$

Let $S_N$ be the number of bits in binary representation of all numbers $< N$.

$$\begin{aligned} S_N &= \sum_{k=1}^{N-1} B_k \\ &= \sum_{k=1}^{N-1} \big(\lfloor \ln k \rfloor + 1\big) \\ \end{aligned}$$

When the binary representations of all numbers from $0$ to $N-1$ is laid out, all the bits can be viewed as being contained in a rectangle of $N$ by $\ln \lfloor N \rfloor + 1$. Subtracting all the leading zeros column by column, we get

$$\begin{aligned} S_N &= N (\lfloor \ln N \rfloor + 1) - \sum_{k=0}^{\lfloor \ln N \rfloor} 2^k \\ &= N (\lfloor \ln N \rfloor + 1) - (2^{\lfloor \ln N \rfloor + 1} - 1) \\ &= N \lfloor \ln N \rfloor - 2^{\lfloor \ln N \rfloor + 1} + N + 1 \\ \end{aligned}$$

Now, recall

$$\begin{aligned} C_N &= N − 1 + \text{ number of bits in binary representation of all numbers} < N \\ &= N - 1 + S_N \\ \therefore C_N &= N \lfloor \ln N \rfloor - 2^{\lfloor \ln N \rfloor + 1} + 2N & \text{!} \\ \end{aligned}$$

$\Box$

Source: Analysis of Algorithm