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