mergesort.java

《算法设计与分析》王晓东编著

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;
		}
	}
	
	public static void mergePass(Comparable[] x,Comparable[] y,int s)
	{   // 合并大小为s的相邻数组
		int i=0;
		while (i<=x.length-2*s)
		{// 合并大小为s的相邻2段子数组
			merge(x,y,i,i+s-1,i+2*s-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];		
	}
	
	public 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=L,
		    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 q=j;q<=r;q++)
				d[k++]=c[q];		
		else
			for (int q=i;q<=m;q++)
				d[k++]=c[q];
	}   
}