mergesort.java

数据结构与算法分析设计的实验作业

public class MergeSort
{
	public	static String printArray(int[] a)
	{
		String result=" ";
		for(int i=0;i<a.length;i++)
		result+=a[i]+" ";
		return result;
	}
	
	public static int[] mergeSort(int[] a)
	{
		int[] b=new int[a.length];
		int s=1;
		
		while(s<a.length)
		{
			mergePass(a,b,s);
			s+=s;
			mergePass(b,a,s);
			s+=s;
		
		}return a;
	}
	
	public static void mergePass(int[] x,int[] y,int s)
	{
		int i=0;
		while(i<=x.length-2*s)
		   {
		    	merge(x,y,i,i+s-1,i+2*s-1);
		    	i=i+2*s;
	    	}
		if(i+s<x.length)
		   merge(x,y,i,i+s-1,x.length-1); 
       else 
            for(int j=i;j<=x.length-1;j++) 
            y[j]=x[j]; 
	}
	
	public static void merge(int[] c,int[] d,int l,int m,int r)
    {
     int i=1,
         j=m+1,
         k=1;
     while((i<=m)&&(j<=r))
       if(c[i]<=c[j])
          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];
    }
	public static void main(String args[])
	{
		int a[]={12,45,22,68,34,89};
		System.out.println("before sort\n"+printArray(a));
    
         a=mergeSort(a);
	
		System.out.println("after sort\n"+printArray(a));
	}
}