1.什么是归并排序？
归并：将两个有序数组合并成一个更大的有序数组。
归并排序有两个主要操作：递归和合并。
要将一个数组排序，可以先（递归的）将它分半分别排序，然后将结果归并起来，这就是归并排序。
我们知道递归的主要思想是分治思想，而这也是归并排序的思想。
2.归并的抽象方法
归并方法主要讲数组左侧（a[lo..mid]）和数组右侧(a[mid+1..hi])归并成一个有序的数组并将结果防止到a[lo..hi]中。
在下面的实现中，我们将借助一个辅助数组aux：
public static void merge(int[] a, int lo, int mid,int hi){
// i代表mid左侧的角标，j代表mid右侧的角标，每次向数组a中放入左侧的元素时i++，向数组a中放入右侧的元素时j++
int i = lo, j= mid;
//将原数组复制到辅助数组中
for(int k = lo;k <= hi; k++){
aux[k] = a[k];
}
for(int k = lo; k <= hi; k++){
//1.左侧用尽取右侧
if(i > mid) a[k] = aux[j++];
//2.右侧取尽取左侧
else if(j>hi) a[k] = aux[i++];
//3.左侧元素大于右侧元素时取右侧
else if(a[i] > a[j]) a[k] = aux[j++];
//4.左侧元素小于右侧元素时取左侧
else a[k] = aux[i++];
}
}
归并完成后，下面要实现递归，递归的顺序有两种方式：
1.自顶向下
2.自底向上
3.自顶向下的归并排序
public class Merge{
private static int[] aux;
public static void sort(int[] a){
//一次性分配空间
aux = new int[a.length];
mergeSort(a,0,a.length - 1);
}
//递归方法
private static void mergeSort(int[] a; int lo; int hi){
//跳出递归的条件
if(lo >= hi) return;
int mid = lo + (hi - lo)/2;
mergeSort(a,lo,mid);//将左侧排序
mergeSort(a,mid,hi);//将右侧排序
merge(a,lo,mid,hi);//归并结果
}
}
4.自底向上的归并排序
这种实现方法比标准的递归代码量更少。首先我们进行的是两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并（将两个大小为2的数组归并成一个大小为4的数组），然后是八八归并...
public class MergeBU {
public static void sort(int[] a) {
int n = a.length;
int[] aux = new Comparable[n];
for (int len = 1; len < n; len *= 2) {
for (int lo = 0; lo < n-len; lo += len+len) {
int mid = lo+len-1;
int hi = Math.min(lo+len+len-1, n-1);
merge(a, aux, lo, mid, hi);
}
}
}
}
自底向上的归并.png
自底向上的归并排序比较适合采用链表的数据，这种方法只需要重新组织链表链接就能将链表原地排序（不需要创建新的链表结点）。
5.复杂度
对于长度为N的数组，归并排序所需的时间和NlogN成正比；它的主要缺点是：所需要的额外空间和N成正比。
