下载掌阅APP，畅读海量书库
立即打开
在数列排序中，如果只有一个数，那么它本身就是有序的；如果只有两个数，那么进行一次比较就可以完成排序。也就是说，数越少，排序越容易。那么，对于一个由大量数据组成的数列，我们很难一次完成排序，这时可将其分解为小的数列，一直分解到只剩一个数时，本身已有序，再把这些有序的数列合并在一起，执行一个和分解相反的过程，从而完成对整个序列的排序。
合并排序就是采用分治策略，将一个大问题分成很多个小问题，先解决小问题，再通过小问题解决大问题。由于排序问题给定的是一个无序序列，所以可以把待排序元素分解成两个规模大致相等的子序列，如果不易解决，则再将得到的子序列继续分解，直到在子序列中包含的元素个数为1。因为单个元素的序列本身是有序的，此时便可以进行合并，从而得到一个完整的有序序列。
合并排序是采用分治策略进行排序的算法，是分治算法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略。
算法步骤如下。
（1）分解：将待排序元素分成大小大致相同的两个子序列。
（2）治理：对两个子序列进行合并排序。
（3）合并：将排好序的有序子序列进行合并，得到最终的有序序列。
给定一个数列(42,15,20,6,8,38,50,12)，执行合并排序的过程如下图所示。
从上图可以看出，首先将待排序元素分成大小大致相同的两个子序列，然后把子序列分成大小大致相同的两个子序列，如此下去，直到分解成一个元素时为止，这时含有一个元素的子序列就是有序的；然后执行合并操作，将两个有序的子序列合并为一个有序序列，如此下去，直到所有的元素都合并为一个有序序列时为止。
为了进行合并，这里引入一个辅助合并函数Merge(A,low,mid,high)，该函数将排好序的两个子序列A[low:mid]和A[mid+1:high]进行合并。其中，low、high代表待合并的两个子序列在数组中的下界和上界，mid代表下界和上界的中间位置，如下图所示。
这里还设置3个工作指针 i 、 j 、 k （整型下标）和一个辅助数组B。其中， i 和 j 分别指向两个待排序子序列中当前待比较的元素， k 指向辅助数组B中待放置元素的位置。比较A[ i ]和A[ j ]，将较小的赋值给B[ k ]，相应的指针同时向后移动。如此反复，直到所有元素都处理完毕。最后把辅助数组B中排好序的元素复制到数组A中，如下图所示。
第1次比较时，A[ i ]=4，A[ j ]=2，将较小的元素2放入数组B中， j ++， k ++。
第2次比较时，A[ i ]=4，A[ j ]=6，将较小的元素4放入数组B中， i ++， k ++。
第3次比较时，A[ i ]=9，A[ j ]=6，将较小的元素6放入数组B中， j ++， k ++。
第4次比较时，A[ i ]=9，A[ j ]=18，将较小的元素9放入数组B中， i ++， k ++。
第5次比较时，A[ i ]=15，A[ j ]=18，将较小的元素15放入数组B中， i ++， k ++。
第6次比较时，A[ i ]=24，A[ j ]=18，将较小的元素18放入数组B中， j ++， k ++。
第7次比较时，A[ i ]=24，A[ j ]=20，将较小的元素20放入数组B中， j ++， k ++。
此时， j >high的后半部分已处理完毕，但前半部分还剩余元素，该怎么办？将剩余元素照搬到数组B就可以了。
完成合并后，需要把辅助数组B中的元素复制到原来的数组A中。
算法代码：
将序列分为两个子序列，然后对子序列进行递归排序，再把两个已排好序的子序列合并成一个有序的序列。
时间复杂度：分解仅仅是计算出子序列的中间位置，需要常数时间 O (1)。递归求解两个规模为 n /2的子问题，所需时间为2 T ( n /2)。合并算法可以在 O ( n )时间内完成。所以总运行时间如下：
当 n >1时，递推求解：
递推最终的规模为1，令 n =2 x ，则 x =log n ，那么
合并排序算法的时间复杂度为 O ( n log n )。
空间复杂度：程序中的变量占用了一些辅助空间，这些辅助空间都是常数阶的，但每调用一个Merge()，都分配一个适当大小的缓冲区，在退出时释放。最多分配的大小为 n ，所以空间复杂度为 O ( n )。递归调用所使用的栈空间等于递归树的深度，递归树如下图所示。
递归调用的底层元素个数为1，因此 n =2 x ， x =log n ，递归树的深度为log n 。