public class Merge {
    //輔助數(shù)組
    private static Comparable[] assist;
    //對(duì)數(shù)組a中的元素進(jìn)行排序
    public static void sort(Comparable[] a){
        assist=new Comparable[a.length];
        int lo=0;
        int hi=a.length-1;
        sort(a,lo,hi);
    }
    //對(duì)數(shù)組a中從lo到hi的元素進(jìn)行排序
    private static void sort(Comparable[] a,int lo,int hi){
        if(hi<=lo){
            return;
        }
        int mid=lo+(hi-lo)/2;
        //對(duì)lo到mid之間的元素進(jìn)行排序
        sort(a,lo,mid);
        //對(duì)mid+1到hi之間的元素進(jìn)行排序
        sort(a,mid+1,hi);
        //對(duì)lo到mid這組數(shù)據(jù)和mid到hi這組數(shù)據(jù)進(jìn)行歸并
        merge(a,lo,mid,hi);
    }
    //對(duì)數(shù)組中，從lo到mid為一組，從mid+1到hi為一組，對(duì)這兩組數(shù)據(jù)進(jìn)行歸并
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //lo到mid這組數(shù)據(jù)和mid+1到hi這組數(shù)據(jù)歸并到輔助數(shù)組assist對(duì)應(yīng)的索引處
        int i=lo;//定義一個(gè)指針，指向assist數(shù)組中開(kāi)始填充數(shù)據(jù)的索引
        int p1=lo;//定義一個(gè)指針，指向第一組數(shù)據(jù)的第一個(gè)元素
        int p2=mid+1;//定義一個(gè)指針，指向第二組數(shù)據(jù)的第一個(gè)元素
        //比較左邊小組和右邊小組中的元素大小，哪個(gè)小，就把哪個(gè)數(shù)據(jù)填充到assist數(shù)組中
        while(p1<=mid&&p2<=hi){
            if(less(a[p1],a[p2])){
                assist[i++]=a[p1++];
            }else{
                assist[i++]=a[p2++];
            }
        }
        //把未填充的數(shù)據(jù)填到assist中
        while(p1<=mid){
            assist[i++]=a[p1++];
        }
        while(p2<=hi){
            assist[i++]=a[p2++];
        }
        for(int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }
    }
    //比較v元素是否小于w元素
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    //數(shù)組元素i和j交換位置
    private static void exchange(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
 
}
//測(cè)試代碼
 class Test{
    public static void main(String[] args) {
        Integer[] a={8,4,6,5,7,1,3,6,2};
        Merge.sort(a);
        System.out.println(Arrays.toString(a));
    }
}