归并算法的基础是，将两个有序的数组归并成一个更大的有序数组。
自然而然想到的就是，创建一个新的数组，将两个不同的有序数组归并到第三个数组中，然后结果返回一个数组。
Java的确可以以数组作为返回值，但是每次归并都创建一个新数组，会带来新的时间和空间上的花销。
比如每次归并都初始化一个新的数组，这是一个时间的花销。至于空间的花销，每次归并创建的数组长度加起来，肯定会比N大。
所以可以直接在排序的开始阶段，直接创建一个长度为N的数组，将排序的部分元素放到该辅助数组中，然后将排序结果放回原数组。
一：一次归并
就是比较两个数组当前元素的大小，小的进入数组。
如果一个数组已经全部进入，那么另一个数组可以直接全部依次进入，因为是有序的。
public static void merge(int []a,int lo,int mid,int hi){
int i = lo;
int j = mid+1;
//将lo----mid和mid+1----hi进行归并
//复制数组到aux里面，方便原地归并
for(int k=lo;k<=hi;k++)
aux[k]=a[k];
//k是元素的总数，k个元素要归并好的
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[i]<aux[j])
a[k]=aux[i++];
//右端的元素比作端的小
else
a[k]=aux[j++];
}
}//end merge
二：自顶向下的归并排序（递归实现）
自顶向下，意味着从整个大数组开始，不断对半分，将左半部分和又半部分的数组归并。
不过当前的两个数组都是无序的，怎么办的？要进行递归，一直递归到单个元素的时候，该数组可以看成有序的，即可返回了。
然后将11归并变成一个2元素有序的数组，然后22归并变成4元素有序的数组................直到n/2的两个数组归并，排序完成。
public static int aux[];
public static void sort(int a[]){
aux = new int[a.length];
sort(a,0,a.length-1);
}
public static void sort(int a[],int lo,int hi){
if(lo>=hi)
return;
int mid = (lo+hi)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
三：自底向上的归并排序（循环实现）
整个递归的归并排序思路是，先递归，一直到元素为1的时候返回，进行归并，再返回。
那么换种方法，我们能不能直接从元素为1的数组入手，一步一步向上归并呢？
答案是肯定的，我们用循环就能实现。
public static void sort2(int a[]){
int N = a.length;
aux = new int [N];
for(int sz = 1;sz<N;sz=sz+sz)//每次的数组长度：1、2、4、8.....
for(int lo=0;lo<N-sz;lo+=sz+sz)//每次归并的起点，要跨两个sz
merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));//一次归并
}
时间复杂度：
可以看出，归并的次数等于将数组对半分的次数。能分一次，就归并一次。所以次数为logN，底数为2。
一次归并的时间，如果包括了复制辅助数组的话，算一个N。后面的每次遍历都会比较，是同时进行的，也是N。总的算2N。
整个的时间复杂度是NlgN级别的。
空间复杂度：
用了一个辅助数组，所以是N。
网上也有常数空间复杂度的归并，但是那种方法，导致时间复杂度退化为了平方级，具体就补不贴代码了。
稳定性：
稳定