归并排序：所需时间为NlogN，但所需额外空间与N成正比。

原地归并：

public static void merge(Comparable[] a, int lo, int mid, int hi){	//将a[lo..mid]和a[mid+1..hi]归并	int i = lo, j = mid + 1;	for (int k = lo; k <= hi; k++)	//将a[lo..hi]复制到aux[lo..hi]		aux[k] = a[k];	for (int k = lo; k <= hi; k++)	//归并回到a[lo..hi]		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] = aux[i++];}

　　基于原地归并，实现了自顶向下的归并排序：

public class Merge{	private static Comparable[] aux;           //归并所需的辅助数组	public 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)	{	//将数组[lo..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的任意数组，自顶向下的归并排序需要0.5NlgN到NlgN次比较。主要缺点是辅助数组所使用的额外空间和N的大小成正比。另外，归并排序在小规模问题中对于递归方法的调用过于频繁，可以使用插入排序处理小规模的子数组（比如长度小于15），再使用归并排序，一般可以将归并排序的运行时间缩短10%到15%。另外，如果a[mid]<=a[mid+1]，则可以跳过merge()方法，这样对于任意有序的子数组算法的运行时间就是线性的。

自底向上的归并排序

public class MergeBU{	private static Comparable[] aux;           //归并所需的辅助数组	public static void sort(Comparable[] a)	{	//进行lgN次两两归并		N = a.length;		aux = new Comparable[N];       //一次性分配空间		for (int sz = 1; sz < N; sz = sz+sz)           //sz子数组大小			for (int lo = 0; lo < N-sz; lo += sz+sz)   //lo:子数组索引				merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1);	}}

　　当数组长度为2的幂时，两种排序方法所用比较次数和数组访问次数相同，还是顺序不同。