import java.util.*;
import java.io.*;
import javax.swing.*;
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];
}
/**/public static void main(String[]args){
String s=JOptionPane.showInputDialog(null,"输入数组大小：",
"MergeSort",JOptionPane.QUESTION_MESSAGE);
int n=Integer.parseInt(s);
//构建数组
Integer[] a=new Integer[n];
//数组赋值及输出
System.out.println("Array a:");
for(int i=0;i<n;i++){
String s1=JOptionPane.showInputDialog(null,"输入a["+i+"]：",
"MergeSort",JOptionPane.QUESTION_MESSAGE);
a[i]=Integer.valueOf(s1);
System.out.print(a[i]+" ");
}
/*Integer[]b=*/mergeSort(a);
//输出完成排序的数组
System.out.println("The Sorted Array :");
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
}
}
