归并排序也称为合并排序，本文详细介绍归并非递归的实现。
有一串乱序的数字，将它们（利用合并排序的思想）排列成有序的。
通常使用一个数组来保存这个串无序的序列，输出也用一个数组来表示
输入：乱序的数组A，数组的长度n
输出：有序的数组A
这张图叙述了合并排序算法的基本思路，类似一棵倒放的二叉树。
图中标记的解释：state0代表初始的状态，经过第一趟合并（merge1）之后得到的状态为State1，以此类推。
在State0初始状态时，两两合并，合并用到的算法是“合并有序的数组 merge sorted array”。即每次合并得到的都是有序的数组。
两两合并的规则是：将两个相同序列长度的序列进行合并，合并后的序列长度double。
第一趟合并（merge 1）调用了4次merge sorted array，得到了4个有序的数组："5, 8"，"3, 9"，"6, 4"，"1, 4"（每个合并后的序列长度为2）
第二趟合并（merge 2）调用了2次merge sorted array，得到了2个有序的数组："3, 5, 8, 9"，"1, 4, 6, 11''（每个合并后的序列长度为4）
按步骤1的思想以此类推，经过多次合并最终得到有序的数组，也就是State3。
可以看出经过一共3趟合并，最终得到有序的数组。
可以看出每趟要执行的合并次数不同，第一趟合并执行4次，第二趟合并执行2次，第三趟合并行1次。
看了上述的算法思想，可以知道算法可以设计成两层循环
- 外层循环遍历趟数
- 内层循环遍历合并次数
下面的伪码描述了两层循环体的实现：
1 merge_sort(A[], n) { 2 while (趟数条件) { // 外层循环：合并的大趟数 3 while (执行合并的条件) { // 内层循环：每趟合并的次数 4 // 进行两两合并 5 } 6 } 7 }
如图可知，一般数组元素的个数不一定是2i个。右边多出的"10, 7, 2"子树可以视作一般情况的情形。
虽然元素个数不一定是2i个，但是任意元素个数的n，必然可以拆分成2j + m个元素的情形（数学条件不去深究）
由图可知，特殊情形思想中的两两合并的规则不能满足一般情况的合并需求
- 图中灰色的箭头代表无需合并，因为找不到配对的元素。
- 图中墨蓝色的箭头代表两个长度不相等的元素也需要进行合
将上述的合并需求称为长短合并，容易知道长短合并仅存在1次或0次。
下面讨论的合并前/后的序列长度特指两两合并后得到的序列长度。
虽然一般情形与特殊情形的合并规则有差别（一般情形复杂），但是可以设计一个通用的合并趟数条件。
设置变量t：记录每趟合并后序列的长度（t=2k），其中k是趟次（如图中的merge1、2、3、4）
- 通过观察发现：每次合并后序列的大小有规律，第一趟后合并的序列大小都是2，第二趟合并后的序列大小都是4，以此类推..
- "10, 7, 2"这三个元素组合而成的序列长度虽然不满足上述的规律，但是并不影响趟数的计算。24 = 16 ≥ 11，4趟后循环结束。
- 可以设计成：if 最后合并后的序列长度≥实际元素的个数n，这时可以说明循环结束
下面的伪代码给出了合并趟数的循环设计，以及循环结束的条件。
1 merge_sort(A[], n) { 2 int t = 1; // t：每趟合并后序列的长度 3 while (t<n) { // 合并趟数的结束条件是：最后合并后的序列长度t≥数组元素的个数n 4 t *= 2; 5 // TODO：每趟进行两两合并 6 } 7 }
从上图可以看出：每趟的合并次数和元素的总数n有关，且和合并前/后的序列长度有关。
数组的元素总数n越大，自然需要合并的次数更多。
每趟合并前序列长度越长，这趟需要合并的次数更少。
设置变量s：记录合并前序列的长度
下面列出了一般情形下的合并数学规律
记m为两两合并的次数（图中每对黑色箭头代表一次两两合并）
记j为长短合并的次数（图中每对墨蓝箭头代表一次长短合并）
第一趟合并 ：n=11，s=1，t=2，m=5，j=0
第二趟合并 ：n=11，s=2，t=4，m=2，j=1
第三趟合并 ：n=11，s=4，t=8，m=1，j=0
第四趟合并 ：n=11，s=8，t=16, m=0，j=1
存在公式：m = n / t，j =(n % t > s ) ? 1: 0 可以设计如下的内层循环
其中第二个公式不太好理解，可以以merge2的合并过程作为参考：
两两合并得到了"3, 5, 8, 9"，"1, 4, 6, 11"两个序列后。还剩余3个元素，因为3>2=s，所以还要进行长短合并。
1 merge_sort(A[], n) { 2 int t = 1; 3 int i; // 每趟合并时第一个序列的起始位置 4 int s; // 合并前序列的长度 5 while (t < n) { 6 t *= 2; 7 i = 0; 8 s = t; 9 while(i + t < n) {// 每趟进行两两合并，结束条件： 10 // TODO：两两合并操作(对两个长度相等的数组进行合并) 11 i = i + t 12 } 13 if (i + s < n) { // 判断：还有两两长度不相同的数组需要合并 14 // TODO：长短合并操作(对于长度不相同的数组进行合并) 15 } 16 } 17 }
1 /** 2 * 归并排序算法 3 * @param A 乱序数组A 4 * @param n 数组A的元素个数 5 */ 6 void merge_sort(int A[], int n) { 7 int i,s; 8 int t = 1; 9 while (t < n) { // 外层循环：合并的大趟数 10 s = t; 11 t *=2; 12 i = 0; 13 while (i + t < n) { // 内层循环：每趟需要合并的次数 14 merge(A, i, i+s-1, i+s*2-1, t); 15 i = i + t; 16 } 17 if (i + s < n) { // 判断还有剩下的元素待处理。 18 merge(A, i, i+s-1, n-1, n-i); 19 } 20 } 21 }
其中merge算法，请查看我的上一篇文章介绍：合并两个有序的数组。下面给出了实现：
1 /** 2 * 合并两个有序的子数组( A[p]~A[q]及A[q+l]~A[r]已按递增顺序排序 ) 3 * @param A 整数数组 4 * @param p 第一个子数组的起始下标 5 * @param q 第一个子数组的末尾下标 6 * @param r 第二个字数组的末尾下标 7 * @param n A数组的元素个数 8 */ 9 void merge(int A[], int p, int q, int r, int n) { 10 int *B = new int[n]; // 建立缓冲区 11 int k = 0; // 指向B的游标，主要用于插入数据进B中 12 int i = p, j = q + 1; 13 while (i <= q && j <= r) { // while循环的跳出条件是：i和j只要有一个超过各种数组的界限 14 if (A[i] >= A[j]) { 15 B[k++] = A[j++]; 16 } else { 17 B[k++] = A[i++]; 18 } 19 } 20 if (i == q+1) { // 说明是前半段先遍历完，把后半段的拼到数组后面 21 while (j <= r) { 22 B[k++] = A[j++]; 23 } 24 } else { 25 while (i <= q) { 26 B[k++] = A[i++]; 27 } 28 } 29 // 将选定的部分替换为B的数组 30 k = 0; 31 for (i = p; i <= r; i++) { 32 A[i] = B[k++]; 33 } 34 delete[] B; 35 }
