归并排序
概论
归并排序的一切都是基于归并这一操作，具体来说就是把两个有序的小数组归并成一个有序的大数组。首先从这两个数组中各按顺序取出一个元素，将小的元素先放入大数组，大的后放入大数组（这里需要辅助数组），然后再重复这个动作，直到我们得到这个有序的大数组，排序完成。当然，当我们需要排序的时候，通常摆在我们面前的是一个数组，而且无序。如果要满足之前的条件——两个有序的小数组，我们首先就要把这个大数组分为两个数组，但是，这两个数组并不是有序的，这时我们有两个选择：
- 继续分下去，也许大家想到了递归，是的，因为当我们分到每个子数组只有一个元素的时候，就已经满足归并的条件了——两个有序的小数组，这也是我们后边代码所采用的方法。
- 通过之前的排序算法（希尔排序，初级排序算法）将这两个数组排序，然后进行归并。（当子数组成为小规模数组时，可以采用这种方法，后面会提到，这是一种改进归并排序中递归算法性能的方法）
图中的a[]与代码中的array[]所对应
自顶向下的归并排序
public class MergeSortUptoDown {
public static int[] aux;//auxiliary 辅助的 数组
public static void sort(int[] array){
aux = new int[array.length];
sort(array,0,array.length-1);
}
private static void sort(int[] array,int lo,int hi){
if (lo>=hi) return;
sort(array,lo,lo+(hi-lo)/2);
sort(array,lo+(hi-lo)/2+1,hi);
merge(array,lo,lo+(hi-lo)/2,hi);
}
//merge的是array[lo]到array[hi]之间的元素
public static void merge(int[] array, int lo, int mid, int hi) {
for (int k=lo;k<=hi;k++){//复制array[lo]到array[hi]之间的元素到aux
aux[k]=array[k];
}
int i = lo;
int j = mid+1;
for (int k = lo;k<=hi;k++){//归并两个子数组
if (i>mid) array[k] = aux[j++];//左数组索引越界
else if (j>hi) array[k]=aux[i++];//右数组索引越界
else if (aux[i]>aux[j])array[k]=aux[j++];
else array[k]=aux[i++];
}
}
}为什么叫自顶向下的归并排序？大家看sort()，首先着眼就是整个数组的排序，就如上面概论中所言，把大数组切成一个个小数组，然后进行归并。这里主要说的是归并的过程，merge()中，首先进行了复制，将需要归并的这段数组复制到辅助数组aux中，然后记录下两个子数组的首位索引i和j，然后真正进入归并，这里考虑了四种情况，1左数组用尽（取右数组元素）2右数组用尽（取左数组元素）3右数组的当前元素小于左数组的当前元素（取右数组元素）4右数组当前元素大于等于左数组当前元素（取左数组元素）
改进归并排序算法 1、对小规模子数组使用插入排序。用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所以改进它们的处理方法就能改进整个算法。而前几篇文章中说到的排序算法比如插入排序非常简单，因此可能在小数组上比归并排序更快。 2、 测试数组是否已经有序。 我们可以添加一个判断条件，如果array[mid]小于array[mid+1]，我们就认为数组是有序的并跳过merge()方法。如此也能够改进算法的性能。
自底向上的归并排序
有自顶向下必有自底向上，自底向上的归并排序，就是先将数组中元素每个元素各成一个子数组，两两进行归并，然后调整子数组的大小为2，两两归并，调为4，两两归并…最终整个数组成为有序数组。
public static void sort(int[] array){
aux = new int[array.length];
for (int sz=1;sz<array.length;sz=2*sz){//sz<N 如果小于N/2 可能漏掉某些元素
for (int i = 0;i<array.length-sz;i=i+2*sz){//i是子数组的索引
merge(array,i,i+sz-1,Math.min(i+2*sz-1,array.length-1));//注意后两个参数，要减一，以及取小
}
}
}自底向上的归并排序比较适用于链表组织的数据，这种方法只需要重新组织链表链接就能将链表原地排序。
注意sz有误，依次应该为1,2,4,8
结语
归并排序是一种渐进最优的基于比较排序的算法。当数组长度为2的幂时，自底向上和自顶向下的归并排序都需要1/2NlgN至NlgN次比较，最多访问数组6NlgN次。当然归并排序的最优并不是结束，还有许多值得我们继续思考的地方，比如归并排序的空间复杂度并不让人满意。
腾讯云开发者
