说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！
1、本节摘要
算法设计的方法有很多。插入排序 使用的是 增量 （incremental）方法：在排好子数组 A [ 1 .. j - 1 ]后，将元素 A [ j ]插入，形成排好序的子数组 A [ 1 .. j ]。
在本节中，要介绍另一种设计策略，叫做“分治法”。下面要用分治法来设计一个排序算法，使其性能比插入排序好的多。学过第4章就可以知道，分治类算法的优点之一是可以利用在第4章中介绍的技术，很容易的确定其运行时间。
2、分治法思想介绍
有很多算法在结构上是 递归 的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关子问题。这些算法通常采用 分治策略 （divide-and-conquer）：将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
归并排序、动态规划算法、贪心算法这些常用的算法都是在“分治法”思想的基础上分析出来的，他们是分治法思想的体现。
分治模式在每一层递归上都有三个步骤：
分解（Divide）：将原问题分解成一系列子问题；
解决（Conquer）：递归地解各个子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。
3、归并排序（合并排序）
归并排序（merge sort）完全依照了 分治策略，直观的操作如下：
分解：将 n 个元素分成各含 n / 2个元素的子序列；
解决：对两个子序列递归地排序；若子问题足够小，则直接求解(对子序列排序时，其长度为1时递归结束，因为单个元素被视为是已排好序的)；
合并：合并两个已排序的子序列以得到排序结果。
归并排序的关键步骤在于合并两个已排序的子序列。这里引入一个辅助过程 MERGE(A, p, q, r) ，其中 A 为数组， p ， q 和 r 都是下标，有 p <= q < r 。该过程假设子数组 A [ p .. q ]和 A [ q + 1 .. r ]都已排好序，并将它们合并成一个已排好序的子数组代替当前子数组 A [ p .. r ]。
MERGE过程的时间代价为Θ(n)，其中n = r - p + 1是待合并的元素个数。下面通过扑克牌的例子说明算法的工作过程：假设两堆牌都面朝上的放在桌上，每一堆都是已排序的，且最小的牌在最上面。我们希望把两堆牌合并成一个排好序的输出堆，且面朝下的放在桌上。合并过程为，在面朝上的两堆牌中，选取顶上两张中较小的一张，将其取出后面朝下的放到输出堆中。重复这个步骤，直到某一输入堆为空时为止。这时把输入堆中余下的牌 面朝下的放入输入堆中即可。从计算的角度来看，每一个基本步骤所花时间是个常亮，因为我们只是查看并比较顶上的两张牌，又因至多进行n次比较，所以MERGE过程的时间复杂度为Θ(n)。
下面的伪代码实现了上述思想，但有一个小的优化，即在两个子堆中增加了∞这个哨兵，来避免检查两个子堆是否为空。一旦出现两个哨兵牌同时出现时，说明两堆牌中非哨兵的牌都已经被放到输出堆中去了，因为预先直到只有r - p + 1张牌会被放到输出堆中去，因此此时也是执行了r - p + 1个基本步骤了，循环可以停止了。
MERGE(A, p, q, r)
1 n1 = q - p + 1
2 n2 = r - q
3 //let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays
4 for i = 1 to n1
5 L[i] = A[p + i - 1]
6 for j = 1 to n2
7 R[j] = A[q + j]
8 L[n1 + 1] = MAX
9 R[n2 + 1] = MAX
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] <= R[j]
14 A[k] = L[i]
15 i = i + 1
16 else
17 A[k] = R[j]
18 j = j + 1
下面说明完整的归并排序过程MERGE-SORT，其中 MERGE 过程作为归并排序中的一个子程序来使用。MERGE-SORT(A, p, r) 对子数组 A [ p .. r ]排序。如果 p >= r ，则该子数组中至多只有一个元素，视为已排序。否则，分解步骤就计算出一个下标 q ，将 A [ p .. r ]分成 A [ p .. q ]和 A [ q + 1 .. r ]，各含 FLOOR(n / 2) 1 个元素。
MERGE-SORT(A, p, r)
1 if p < r
2 q = (p + r) / 2
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
下图自底向上地展示了当 n 为2的幂时，整个过程中的操作。算法将两个长度为1的序列合并成已排好序的、长度为2的序列，接着又将长度为2的序列合并成长度为4的序列，直到最终形成排好序的 n 的序列。
4、归并排序时间复杂度分析
这里只说明分析结果，分析过程请参考《算法导论(原书第二版)》。归并排序 的总代价为cn(lgn + 1) = cn * lgn + cn，忽略低阶项和常亮c，即得到结果Θ(n * lgn)。
需要说明的是，忽略低阶项和常亮c的前提是输入规模n很大。使用归并排序时一般输入规模都很大，输入规模很小时一般采用的是插入排序。
5、练习
二分查找伪码：
BINARY-SEARCH(A, v)
1 front = 1
2 end = A.length
3 while front < end
4 middle = (front + end) / 2
5 if A[middle] < v
6 front = middle + 1
7 else if A[middle] > v
8 end = middle - 1
9 else
10 return middle
11 return -1
6、参考文档
合并排序，该文章中的两点改进很好：1）、分割为合适长度的小序列后使用插入排序，然后将经过插入排序的小序列进行合并排序；2）、算法中对两个小序列进行合并操作之前，先对其中值点进行比对，如果符合期望的升/降序目标，则不用再经过合并操作，直接连接起来即可。
