public class MergeSort {
	
	public static void mergeSort(Comparable[]a)
	{
		Comparable[]b=new Comparable[a.length];
		int s=1;
		while (s<a.length)
		{
			mergePass(a,b,s);//合并到数组b
			s+=s;
			mergePass(b,a,s);//合并到数组a
			s+=s;
		}
	}

	private static void mergePass(Comparable[] x, Comparable[] y, int s) 
	{//合并大小为s的相邻数组
		int i=0;
		while (i<=x.length-2*s) 
		{//合并大小为s的两端相邻字数组
			merge(x,y,i,i+s-1,i+s*2-1);
			i=i+2*s;
		}
		//剩下的元素个数小于2s
		if (i+s<x.length) 
		{
			merge(x, y, i, i+s-1, x.length-1);
		}
		else//复制到y 
		{
			for (int j = i; j < x.length; j++) 
			{
				y[j] = x[j];
			}
		}
	}

	private static void merge(Comparable[] c, Comparable[] d, int l, int m, int r) 
	{
		//合并c[l:m]和c[m+1,r]到d[l:r]
		int i=1, j=m+1,k=l;
		while (i<=m && j<=r) 
		{
			if (c[i].compareTo(c[j])<=0)
			{
				d[k++]=c[i++];
			}
			else
			{
				d[k++]=c[j++];
			}
		}
		
		if (i>m)
		{
			for (int k2 = 0; k2 <=r; k2++) 
			{
				d[k++] = c[k2];
			}
		}
		else
		{
			for (int k2 = 0; k2 <=m; k2++) 
			{
				d[k++] = c[k2];
			}
		}
	}
}