有一串乱序的数字，将它们（利用合并排序的思想）排列成有序的。
通常使用一个数组来保存这个串无序的序列，输出也用一个数组来表示
输入：乱序的数组A，数组的长度n
输出：有序的数组A
特殊情形(元素个数为2i) 基本思路：看作是一颗倒过来的满二叉树，两两成对
这张图叙述了合并排序算法的基本思路，类似一棵倒放的二叉树。
图中标记的解释：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 }