【七类排序】之第六种：归并排序

感谢之前的同学给我指出的错误， 我之前太自信以至于代码都是裸敲上去的，本着对各位负责的态度，以后我将会事先把程序编译验证通过。
注：若无特殊说明， 排序目的为递增。

坦白来说，我很讨厌这个算法，虽然很好实现， 很好理解， 虽然理论时间复杂度是严格的n times log（n） base 2（because T(n) = 2T(n/2) + n-1 ）, 虽然相比于快速排序来说是有常数时间的优势。但是，希望各位读者明白一个事实，理论时间复杂度并不等于执行的复杂度， 尤其是当你意识到计算机里还有cache这个概念就会了然。 在nlogn这个级别的算法中 ， 实际速度最快的就是quicksort， 笔者曾经做过大规模数据实验，当元素大于1000W的时候会有显著的差别，不考虑特殊的数据情况速度由快到慢依次是 quicksort， mergesort， heapsort。  最后一个是堆排序，笔者并没有写。  这里也征求下意见， 第七篇笔者打算在堆排序算法和线性排序算法中选一个写， 笔者是更加偏向后者， 因为笔者打算涉及到n^2, nlogn与n的所有排序算法。

言归正传，何为归并排序（Merge Sort）? 我们先引入一个问题： 两个有序好的数组， 如何合并成一个有序数组？

直接说算法步骤：
1： 比较两个数组的头元素， 将较小的元素（也就是当前两数组最小的元素）从原有数组删除，并排入新数组中；
2： 重复步骤1， 直到任一个数组元素个数为0。
3： 如果还有数组含有元素， 那么原封不动接在新数组的尾部。
最终我们得到了合并后的有序数组。

举例说明， 将两个有序数组a={1,5,7}  b={0,4,6,8,9}合并成一个有序数组c, 每次比较a和b的头元素，较小（用红色字体标出）的元素插入c
step 1:
a={1,5,7}
b={4,6,8,9}
c={0}

step 2:
a={5,7}
b={4,6,8,9}
c={0,1}


step 3:
a={5,7}
b={6,8,9}
c={0,1,4}


step 4:
a={7}
b={6,8,9}
c={0,1,4,5}


step 5:
a={7}
b={8,9}
c={0,1,4,5,6}


step6
a={}
b={8,9}
c={0,1,4,5,6,7}


此时此刻， 数组a已经为空， b数组还剩2元素， 直接接在c后面即可， 得到
a={}
b={}
c={0,1,4,5,6,7,8,9}
完毕。

以上是归并算法的精髓思想之一，叫做归并（Merge），时间复杂度显然为线性。 有了这个背景知识， 我们发觉， 1：如果一个数组的左半部分和右半部分都有序， 那么只要通过Merge步骤， 就能在线性时间复杂度内实现全部有序； 2： 单独一个元素本身就是有序； 提示到这里， 读者已经恍然大悟了， 递归！分治！ 归并！  又是一个divide and conquer思想的典型算法， 只不过归并算法中的conquer具体化变成了Merge而已。


于是我们的算法核心部分呼之欲出               private void Sort(int[] a, int left, int right) {
                if (left < right) {
                        int mid = (left+right) / 2;
                        //递归sort左半部分
                        Sort(a, left, mid);
                        //递归sort右半部分
                        Sort(a, mid+1, right);
                        //合并成一个有序数列
                        Merge(a, left, mid, right);
                }
        }

期中left，mid, right是待排序数组的第一个， 中间和最后一个元素。 非常好理解， 那么Merge如何实现呢？ 也非常简单， 用两个索引变量从头往后扫描待归并的两个数组即可。
归并代码如下：

         private void Merge(int[] n, int start, int middle, int end) {

                int p1=start, p2=middle+1;

                int [] temp = new int[end - start +1];

                int ptemp = 0;

                //比较和选择最小的元素插入新数组中。 直到任一数组为空

                while (p1<=middle & p2<=end) {

                        if (n[p1]<n[p2]) temp[ptemp++] = n[p1++];

                        else temp[ptemp++] = n[p2++];

                }

                //若存在数组还有剩余元素， 原封不动接在新数组尾部即可

                while (p1<=middle)

                        temp[ptemp++] = n[p1++];

                while (p2<=end)

                        temp[ptemp++] = n[p2++];

                //将临时数组temp的结果更新回原数组n []

                for (int i = start; i<=end; i++)

                        n = temp[i-start];

        }

这是最常见也是最臃肿的代码， 其实也没什么可以简化的了。 相信各位读者也注意到了， Merge函数中每次都要开辟一个Temp数组，每次都要更新回原数组， 这使得运行时计算机要成几何倍数的多运算，这也是归并排序实战不如quicksort的瓶颈所在。在算法导论一书第二章描述了许多重要的算法包括heapsort, quicksort和linear sort， 但是同为nlgn的Mergesort并没有列入在内， 而是与insertion sort进行对比和引导式学习， 笔者私人推测这个现象也侧面体现了这个算法的效果。anyway, 笔者自己研究过实现方式的常数项的优化，但效果并不显著， 这里就不贴出来了， 主要还是以了解思想为主。

补充几点，各个算法都有自己的优缺点，并不能单独从运行的时间上就说quicksort比mergesort要好，mergesort的很多特性是quicksort代替不了的，：

1. 首先，mergesort的复杂度是严格的O(nlogn)，但对于quicksort，其平均复杂度是O(nlogn)，但是在最unlucky的情况下，复杂度会达到O(n^2)。这个特点有什么关系呢？对于一些敏感的医疗仪器，不确定时间的算法是不被推荐的，因为它能接受程序运行的稍慢一些，但不能接受程序运行的时间出现太大波动。

2.mergesort是stable的但quicksort不是。什么是stable呢？就是sort前如果两个元素相等，那么他们在sort以后顺序不变。mergesort的stable特性能够让它支持多次sort的特性，比如说windows程序系统中，我们先按文件名排序，再按文件类型排序。就能得到先按文件类型排好，相同文件类型的文件再按文件名来排的结果。

3.mergesort能支持类似磁带机的数据访问形式，也就是在必须进行sequence access而不支持random access（如内存）的情况下，mergesort也能工作。这个特性有什么用呢？简单说来，mergesort能够直接对链表进行就地排序，而不用申请额外的一篇内存空间（感兴趣的同学可以写一下这个算法^_^，据同学说这个是他面试yahoo时候的一道面试题，面试官让他写一个算法对linkedlist进行排序，用constant的空间，他没想起要用mergesort，结果就跪了）。对于大数据来说，这个特性很重要，当我们内存中存放不下所有数据的时候，我们不得不把暂时得到的中间数据保存到disk上，disk是以block的形式来访问的，这个时候，就必须要用mergesort。另外，对于distributed system，一次计算都是分布到不同的机器上去完成的，这个时候，也必须要用mergesort

哈哈，是不是因为觉得mergesort太简单了没有技术含量，所以不喜欢

zengxinzhy 发表于 2013-3-8 22:47
补充几点，各个算法都有自己的优缺点，并不能单独从运行的时间上就说quicksort比mergesort要好，mergesort的 ...

quicksort 可以是 stable的，只要寫代碼的時候注意一下即可

brilight 发表于 2013-3-9 12:27
quicksort 可以是 stable的，只要寫代碼的時候注意一下即可

能不能给个思路，我们老师讲课的时候给我们说的就是quicksort是unstable的

brilight 发表于 2013-3-9 12:27
quicksort 可以是 stable的，只要寫代碼的時候注意一下即可

找到了^_^：

Another, less common, not-in-place, version of quicksort uses O(n) space for working storage and can implement a stable sort. The working storage allows the input array to be easily partitioned in a stable manner and then copied back to the input array for successive recursive calls. Sedgewick's optimization is still appropriate.

zengxinzhy 发表于 2013-3-9 14:21
找到了^_^：

Another, less common, not-in-place, version of quicksort uses O(n) space for workin ...

我理解的稳定和不稳定就是个< >和<= >=判断的区别。 当然在我的代码版本里后者会对别的变量带来影响， 所以干脆就不稳定算了。

赞， 有个小细节，int mid = (left+right) / 2; 为了防止溢出可以写成 int mid=left-(left-right)/2