public class MergeSort {
    public static void main(String[] args) {
        int a[]={10,9,8,7,6,5,4,3,2,1};
        mergeSort(a,0, a.length-1);
        for(int i=0;i< a.length;i++){
            System.out.print(a[i]+" ");
        }

    }

    //归并并排序
    public static void mrge(int[] a,int left,int mid,int right){
        int[] temp = new int[a.length];
        int p1=left;
        int p2=mid+1;
        int p3=0;
        while(p1<=mid&&p2<=right){
            temp[p3++]=(a[p1]>=a[p2])?a[p1++]:a[p2++];//这里可以该从小到大还是从大到小
        }
        while(p1<=mid){
            temp[p3++]=a[p1++];
        }
        while(p2<=right){
         temp[p3++]=a[p2++];
        }

        //临时的数组复制到原先的数组
        for(int i=0;i<p3;i++){
            a[left+i]=temp[i];
        }
    }

    //把数组分成子序列
    public static void mergeSort(int[] a,int left,int right){//这个方法是要调用的
        if(left<right){//数组元素不是一个的情况
            int mid=(left+right)/2;
            mergeSort(a,left,mid);
            mergeSort(a,mid+1,right);
            mrge(a,left,mid,right);
        }
    }

}