总结
归并排序主要用了分治的思想，通过将数组分成较小的段，对小段进行排序然后将小段合并起来，从而完成排序。归并排序的时间复杂度是O(nlgn),可以证明nlgn是所有基于比较的算法效率的上限
在看书的过程中，发现自己的代码风格太幼稚，例如：我写 a[i] = aru[j];j++;而在算法书上只要一句 a[i] = a[j++];就搞定了。原因可能是自己在这方面没有思考，老是觉得把功能写好就行了，对这些用法没有深入的理解。
例如for循环中，第一项用于声明变量，第二项是个布尔表达式，在第二项可以进行一些除边界判断的判断，第三项是每个循环完成后的操作，利用这些特性可以使自己的代码更加简洁。
merge归并数组的函数
/*
* 原地归并的抽象方法，用于将两个相临、有序的序列归并
*/
public static void merge(Comparable[] a,int lo,int mid,int hi){
int i = lo,j = mid+1;
for(int k=lo;k<=hi;k++) aux[k] = a[k];//将传入的数组复制
for(int k=lo;k<=hi;k++){
if(less(aux[j],aux[i])) a[k]=aux[j++];
else if (i>mid) a[k]=aux[j++];
else if(j>hi) a[k]=aux[i++];
else a[k]=aux[i++];
}
自顶向下的归并排序
主要思想：利用递归的方法分解，归并
/*
* 自顶向下的归并排序
* 基本思想：分治法，将数组分为较小的快排序再合并
*/
public static void mergeSort(Comparable[] a){
aux = new Comparable[a.length];
int lo = 0,hi = a.length;
mergeSort(a, lo, hi);
}
/*
* 分解、合并数组
*/
public static void mergeSort(Comparable[] a,int lo,int hi){
if(hi<=lo) return;
int mid =lo + (hi-lo)/2-1;
mergeSort(a, lo, mid);
mergeSort(a, mid, hi);
merge(a,lo,mid,hi);
}
自底向上的归并排序
主要思想：先将数组分解再归并
/*
* 自底向上的归并排序
* 基本思想：分治法，先将数组分为小块再合并
*/
public static void bottomMergeSort(Comparable[] a){
int N = a.length;
aux = new Comparable[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,Math.min(lo+sz+sz-1,N-1));
}
