归并排序算法的实现与分析
归并排序
一.雏形思想
- 归并排序
所谓归并排序，关键在于“归并”二字。归并这一行为，本质上就是对两个有序数组（链表…等）进行有序合并成为了一个有序的大数组（链表等）。
由此受到启发，当我们需要对一个大数组进行排序的时候：先将一个大数组分成两个小数组，再将两个已经有序的小数组进行有序合并。
其中有序小数组是递归归并得到的。
建立了归并思想之后，最简单的实现方法就是将两个不同的有序数组归并到第三个数组中——
创建一个适当大小的数组，然后将两个输入数组的元素一个个从小到大放入这个数组中。
- 原地排序
①原因
对归并排序来说：如果对Merge的每个递归调用都声明一个临时数组，那么任一时刻可能会有logN个临时数组处于活动期,这对小内存机器是致命的。
另一方面，如果Merge动态分配并释放最小量临时空间，那么由malloc占用的时间会很多。
由于Merge位于MSort的最后一行，可以在MergeSort中建立该临时数组。因此在任一时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分；我们将使用和输入数组array相同的部分。
这样的话，该算法的空间占用为N，N是待排序的数组元素个数。
上段文字摘自于《归并排序及其空间复杂度的思考》
②原地归并抽象方法
在原因分析中说明了我们可以建立一个临时数组，任意时刻，我们只是使用这个临时数组的某一部分进行排序。
原地归并的抽象化——merge(a,lo,mid,hi)，将子数组a[lo…mid]和a[mid+1…hi]归并成一个有序的数组并将结果存放在a[lo…hi]中，
将涉及的所有元素复制到一个辅助数组中，再把归并的结果放回原数组中。
void merge(int a[], int lo, int mid, int hi){
int i = lo,j = mid+1;//维护的两个指针
for(int k = lo;k <= hi;k++)
aux[k] = a[k];//将a[lo..hi]中的元素复制到aux[lo..hi]中
for(int k = lo;k <= hi;k++){
if(i>mid)
a[k] = aux[j++];
else if(j>hi)
a[k] = aux[i++];
else if(aux[j] <aux[i])
a[k] = aux[j++];
else
a[k] = aux[i++];
}
}
上述方法先将所有元素复制到aux[]中，然后再归并回a[]中。方法在归并时（第二层for循环）进行了4个条件判断：左半边用尽（则取右半边的元素）、右半边用尽（则取左半边的元素）、右半边的当前元素小于左半边的当前元素（则取右半边的元素）以及右半边的当前元素大于等于左半边的当前元素（则取左半边的元素）。
代码中第三个判断分支的比较符号选用小于而非小于等于是有原因的，说明程序在左半边和右半边的当前元素相同的前提下是优先选取左半边的元素。
——这样保证了***排序的稳定性***。
二. 自顶向下的归并排序
自顶向下的思想，就是站在一个宏观的角度去思考问题的解决。
在数组排序的例子中，一言以蔽之，将一个数组先分成两个有序的子数组，再对这两个有序子数组进行归并操作合成一个大的有序数组。
自顶向下的思想多用在递归实现上，且代码结构很清晰，很好组织。
- 算法伪代码
void sort(int a[], int lo, int hi){
if(hi<=lo)
return ;//对应的是只有一个元素的子数组，默认有序
int mid = (lo + hi) / 2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
【重要性】：这段代码也是归纳证明算法能够正确将数组排序的基础：如果它能将两个子数组排序，就能够通过归并两个子数组来将整个数组排序。
- 自顶向下的归并排序的调用轨迹
以对一个含有16个元素的数组排序为例：
sort(a,0,15)
sort(a,0,7)
sort(a,0,3)
sort(a,0,1)
merge(a,0,0,1)
sort(a,2,3)
merge(a,2,2,3)
merge(a,0,1,3)
sort(a,4,7)
sort(a,4,5)
merge(a,4,4,5)
sort(a,6,7)
merge(a,6,6,7)
merge(a,4,5,7)
merge(a,0,3,7)
==========左半部分排序完成=====================
sort(a,8,15)
sort(a,8,11)
sort(a,8,9)
merge(a,8,8,9)
sort(a,10,11)
merge(a,10,10,11)
merge(a,8,9,11)
sort(a,12,15)
sort(a,12,13)
merge(a,12,12,13)
sort(a,14,15)
merge(a,14,14,15)
merge(a,12,13,15)
merge(a,8,11,15)
============右半部分排序完毕=====================
merge(a,0,7,15)
根据上面的轨迹图，实质上起到排序作用的是merge函数，而sort函数的作用在于安排多次merge()方法调用的正确顺序。
- 改进措施
（1）对小规模子数组使用插入排序
用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使得小规模问题中方法的调用过于频繁，所以改进对它们的处理方法就能改进整个算法。
在排序问题中，我们已知插入（或选择）排序十分简单，因此很可能在小数组上壁归并排序更快。
使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%-15%。
void sort(int a[],int lo,int hi){
if(hi <= lo + CUTOFF-1){//CUTOFF就是自定义的小数组长度
InsertionSort(a,lo,hi);
return ;
}
int mid = lo + (ji - lo) / 2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
（2）测试数组是否已经有序
我们可添加一个判断条件，在每次递归时若a[mid]≤a[mid+1]，我们就认为数组已经是有序的并且跳过merge方法。
这个改动并不会影响整体排序的递归调用，但是任意有序的子数组算法的运行时间就变为线性的了。
如果两个子数组的拼接本身就已经是有序的了，那么是不需要进行merge操作的。
void sort(int a[],int lo,int hi){
if(hi <= lo)
return ;
int mid = lo + (hi - lo) / 2;
sort(a,lo,mid);
sort(a,mid+1,hi);
if(a[mid+1]<=a[mid])//如果已经有序，在此处判断之后直接返回
return ;
merge(a,lo,mid,hi);
}
三. 自底向上的归并排序
- 归并排序的两种思想
①自顶向下的归并（递归）
递归实现的归并排序是分治思想的典型应用——将一个大问题分割成小问题分别解决，再用小问题的答案来解决整个大问题。
②自底向上的归并
先归并那些微型数组，再成队归并得到的子数组。直到我们将整个数组归并在一起。
首先进行两两归并，再四四归并，再八八的归并，一直下去。在每一轮归并中，最后一次归并的第二个子数组可能比第一个子数组要小。
这种方法比递归实现的归并排序代码量要更少。
- 算法伪代码
void sort(int a[]){
int N = a.length();//这里是伪码表示，具体求数组长度要根据数据结构决定
for(int sz = 1;sz <N;sz += sz){
for(int lo = 0;lo < N - sz;lo += sz+sz){
merge(a,lo,lo+sz-1,min(lo+sz+sz-1,N-1));//防止上界越界
自底向上的归并排序会多次遍历整个数组，根据子数组大小进行两两归并。
子数组的大小sz的初始值为1，每次加倍。最后一个子数组的大小只有在数组大小是sz的偶数倍的时候才会等于sz，否则会比sz小。
- 调用轨迹
依然以长度为16的数组进行排序为例进行轨迹分析
============sz = 1====================
merge(a,0,0,1)
merge(a,2,2,3)
merge(a,4,4,5)
merge(a,6,6,7)
merge(a,8,8,9)
merge(a,10,10,11)
merge(a,12,12,13)
merge(a,14,14,15)
==========sz = 2======================
merge(a,0,1,3)
merge(a,4,5,7)
merge(a,8,9,11)
merge(a,12,13,15)
===========sz = 4====================
merge(a,0,3,7)
merge(a,8,11,15)
===========sz = 8====================
merge(a,0,7,15)
参考
《算法第四版》-归并排序