归并排序在对数组排序的过程中，现递归的分为两半排序，再将结果归并起来。
实现归并的一种直截了当的方式是将两个不同的有序数组归并到第三个数组，但是当用归并对大数组排序时，我们往往需要很多次归并，因此在每次归并时都创建一个新数组来存储排序结果会带来问题。因此我们希望可以实现原地的归并排序算法，在数组中移动而不需要额外的空间。
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++) //将数组a复制到数组aux
aux[k] = a[k];
for(int k = lo; k<=hi; k++) //归并回到数组a
if (i>mid) a[k] = aux[j++];
else if (j>hi) a[k] = aux[i++];
else if(less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = a[i++];
}
以上代码为抽象化的原地归并，而通过分治思想，可以基于这种原地归并的抽象实现自顶向下的归并排序：
public class Merge{
private static Comparable[] aux; //归并所需的辅助数组
private static void sort(Comparable[] a){ //一次性分配空间
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi){
if( hi<= lo) return;
int mid = lo +(hi-lo)/2;
sort(a, lo, mid); //左半侧排序
sort(a, mid+1, hi); //右半侧排序
merge(a, lo, mid, hi); //归并结果
}
}
针对自顶向下的归并排序，可以证明以下命题:
对于长度为N的任意数组，自顶向下的归并排序需要1/2NlgN到NlgN次比较,且最多需要访问数组6NlgN次。
通过上述命题我们知道，归并排序所需要的时间和NlgN成正比，相较于插入排序或是选择排序有了很大提升；而它的主要缺点是所使用的额外空间与和数组大小N成正比。
实现归并的另一种方法是先归并那些微型数组，然后再成对归并得到子数组，并最终将整个数组归并在一起。这种自底向上的归并排序相比原先的归并排序代码量更小。首先我们两两归并，然后四四归并，并一直下去。
public class MergeBU{
private static Comparable[] aux;
public static void sort(Comparable[] a){
int N = a.length;
aux = new Comparable[N];
for( int sz = 1; sz < N; sz = 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));
}
}
当数组长度为2的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数是一样的，只是顺序不同。
自底向上的归并排序比较适合用链表组织的数据。链表先按大小为1的子链表进行排序，然后是大小为2的…… ** 这种方法不需要创建任何新的结点，只需要重新组织链表连接就能将链表原地排序 **
无论是选择，插入，希尔还是归并算法，都是基于比较的算法，它们对于数组的操作是由主键比较决定的。一个基于比较的算法在两次比较之间可能会进行任意规模的计算，但它只能通过比较来获得某个主键的信息。
针对基于比较的排序算法，我们有以下命题
没有任何基于比较的算法能够保证使用少于lg(N!) ~ NlgN次比较将长度为N的数组排序
