（1）分解原问题为若干个子问题。归并排序中将n个元素分解为n/2个元素。
（2）解决这些子问题，递归求解各个子问题。在归并排序中是递归排序两个子序列。
（3）合并这些子问题的解从而形成原问题的解。在归并排序中将两个已排序的子序列合并产生一个已排序的答案。
2、归并排序（merge sort）具体分析： （1）关键关键在于“合并”两个已经排序好的子序列。
（2）引入辅助过程和两个子数组引入一个辅助过程MERGE(A,p,q,r)，其中p、q、r均为下标，满足p<=q 以分排试卷为例，目标是将两叠排序好的试卷堆A(1009890)和B(999592)合并成C堆，第一步比较最下面的试卷，抽出更大的（第一步是抽出100分的卷子）给C堆，后面几步都和第一步一样，从而最终的C堆就是从高到低排出来的六张试卷。 此时引入空白卷（0分），0分放在的是两堆卷子的最上面，当0分显露的时候，这不可能是更低的卷子，除非两张0分都露了出来，但是这种情况的发生意味着所有卷子已经排好。 我们设A堆为A[1...3]，B堆为A[4...6],即p = 1,q = 3, r = 6，后面验证伪代码的时候可以将这些数字代入进去。 给出我们的伪代码： 【1】两个for循环以外部分都是常量时间 【2】第一个for循环需要Θ(n1+n2)=Θ(n),其中n = r - p + 1 【3】第二个for循环迭代n次，每次迭代均需要常量时间 因此其运行时间为Θ(n) 【1】数学知识铺垫 【2】下面通过MERGE-SORT来排序子数组中A[p...r]中的元素：当p >= r,子数组最多有一个元素，所以已经排序完成；当p < r，将A分成两个子数组A[p...q]和A[q+1...r]，然后通过伪代码完成对子数组的排序。 【3】为了排序整个序列A = ，我们调用MERGE-SORT(A,1,A.length)，其中A.length=2ⁿ ，这就形成了一个递归结构，返回时先将两个1项子数组的合并成2项的子数组，再将两个2项子数组的合并成一个4项的子数组，依此类推...下图为A=<5,2,4,7,1,3,2,6>里归并排序的操作。 假设T(n)为规模为n的一个问题的运行时间。 ①问题规模足够小的时候，比如n<=常量c，那么直接求解需要常量的时间，此时运行时间为Θ(1)。 ②问题规模大的时候，将原问题分解为a个子问题，得每个子问题规模为原来的1/b(在归并排序中a=b，但是往往a!=b)，因此我们需要aT(n/b)时间来解决这些子问题。假设分解成子问题需要时间D(n)，合并子问题解成原问题需要C(n),因此得到下图式子 （1）分解：分解步骤仅需计算子数组的中间位置，需要常量时间，因此D(n) = Θ(1) 解决：递归求解两个规模均为n/2的子问题，将贡献2T(n/2)的运行时间 合并：上面的MERGE运行时间为Θ(n)，那么C(n) = Θ(n) （2）C(n) + D(n) = Θ(n)，因为两者相加本质上是一个线性函数，因此与解决的步骤相加，得 事实上T(n)为Θ(lgn)，lgn代表 下面来理解这个原理，先将T(n)改写为 下图为递归树 解释： 【1】顶层的代价为cn，在后面几幅图中被扩展为递归树，第二层的代价为cn/2，第三层为cn/4（结合T(n)的表达式可以看出）...一直到问题规模下降到1，即代价为c。 【2】我们可以发现这时候的树高为lgn（即log2 (n)），有lgn+1层，每层代价为cn，因此Total = (lgn + 1) * cn = cn lgn + cn，因此忽略低阶项和常数后结果为 Θ(nlgn)MERGE(A,p,q,r)
//写出n1和n2的数量
n1 = q - p + 1
n2 = r - q
//让两个数组合并成一个数组
Let L[1..n1+1] and R[1..n2+1] be new arrays
//分别将A中两个子序列赋值给数组L和R
for i = 1 to n1
L[i] = A[p + i - 1] //从A的第p位开始赋值
for j = 1 to n2
L[j] = A[q + j] //从A的第q+1位开始赋值
//引入两张零分试卷
L[n1+1] = 0
R[n2+2] = 0
i = 1
j = 1
//比较各自最大的试卷，抽出更大的
for k = p to r
if L[i] >= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
（5）理解MERGE的运行时间
