1.执行流程

原始序列：49 38 65 97 76 13 27

1）将原始序列看成7个只含有一个关键字的子序列，显然这些子序列都是有序的。

子序列1：49

子序列2：38

子序列3：65

子序列4：97

子序列5：76

子序列6：13

子序列7：27

2）两两归并，形成若干有序二元组，即49和38归并成{38 49}，65和97归并成{65 97}，76和13归并成{13 76}，27没有归并对象，保持原样。第一趟二路归并排序结束，结果如下：

{38 49}，{65 97}，{13 76}，{27}

3）再将这个序列看成若干二元组子序列。

子序列1：38 49

子序列2：65 97

子序列3：13 76

子序列4：27

最后一个子序列长度可能是1，也可能是2。(www.daowen.com)

4）继续两两归并，形成若干有序四元组（同样，最后的子序列中不一定有4个关键字），即{38 49}和{65 97}归并形成{38 49 65 97}，{13 76}和{27}归并形成{13 27 76}。第二趟二路归并排序结束，结果如下：

{38 49 65 97}，{13 27 76}

5）最后只有两个子序列了，再进行一次归并，就可完成整个二路归并排序，结果如下：

13 27 38 49 65 76 97

由以上分析可知，归并排序可以看作一个分而治之的过程（关于分治法，可以看本书最后一章的讲解）：先将整个序列分为两半，对每一半分别进行归并排序，将得到两个有序序列，然后将这两个序列归并成一个序列即可。假设待排序列存在数组A中，用low和high两个整型变量代表需要进行归并排序的关键字范围，由此可以写出如下代码：

2.性能分析

（1）时间复杂度

归并排序中可选取函数merge（）内的“归并操作”作为基本操作。函数merge（）的作用是将两个有序序列归并成一个整体有序的序列。“归并操作”即为将待归并表中的关键字复制到一个存储归并结果的表中的过程。在顺序表中，函数merge（）的“归并操作”执行次数为要归并的两个子序列中关键字个数之和，这在线性表一章有所体现。由归并排序的过程可知：

第1趟归并需要执行2×（n/2）=n次基本操作（其中，2为两子序列关键字个数之和，n/2为要归并的子序列对的个数；每个子序列对执行一次函数merge（），也就是两次基本操作）。

第2趟归并需要执行4×（n/4）=n次基本操作。

第3趟归并需要执行8×（n/8）=n次基本操作。

第k趟归并需要执行2^k×n/2^k=n次基本操作。

当n/2^k=1时，即需要归并的两个子序列长度均为原序列的一半，只需执行一次函数merge（）归并排序即可结束。此时k=log₂n，即总共需要进行log₂n趟排序，每趟排序执行n次基本操作，因此整个归并排序中总的基本操作执行次数为nlog₂n，时间复杂度为O（nlog₂n）。

可见归并排序时间复杂度和初始序列无关，即平均情况下为O（nlog₂n），最好情况下为O（nlog₂n），最坏情况下为O（nlog₂n）。

（2）空间复杂度

因归并排序需要转存整个待排序列，因此空间复杂度为O（n）。