2.3-1
| 3 9 26 38 41 49 52 57 |
| 3 26 41 52 | 9 38 49 57 |
| 3 41 | 26 52 | 38 57 | 9 49 |
| 3 | 41 | 52 | 26 | 38 | 57 | 9 | 49 |
2.3-2
MERGE(A, p, q, r)
1 n_1 = q - p + 1
2 n_2 = r - q
3 let L[1.. $n_1$ ] and R[1..$n_2$] be new arrays
4 for i = 1 to n_1
5 L[i] = A[p + i - 1]
6 for j = 1 to n_2
7 R[j] = A[q + j]
8 i = 1
9 j = 1
10 for k = p to r
11 if i > n_1
12 A[k] = R[j]
13 j = j + 1
14 elseif j > n_2
15 A[k] = L[i]
16 i = i + 1
17 elseif L[i] <= R[j]
18 A[k] = L[i]
19 i = i + 1
20 else
21 A[k] = R[j]
22 j = j + 1
2.3-3
T(n)可被写成
n
/ \
/ \
T(n/2) T(n/2)
同理，T(n/2) 可被写成
n/2
/ \
/ \
T(n/4) T(n/4)
写成树的形式，最后一层都是2。那么最后一行有多少个2呢？
第一层有1个n，第二层有2个n/2，设最后一层有x个2，则2=n/x，因此x=n/2
每层的数字之和都是n。
一共有多少层呢？
我们看看每层数字的分母，第一层是$1=2^0$，第二层是$2=2^1$，第三层是$4=2^2$，……而最后一层是的分母是n/2。由于 $n=2^{\lg n}$ 所以 $n/2=2^{\lg n-1}$ ，从 0到 $\lg n-1$ ，一共 $\lg n$ 层，因此 $T(n)=n \lg n$