public class e归并排序 {
    //思路：利用先递归，后执行的原理
    //     先递归会将数组分解成无数小数组；递归完毕后，开始从后往前执行程序
    //     比较前后两个小数组，利用双指针指向前后两个数组从小到大放到辅助空间
    //     遍历辅助空间元素返回数组
    public static void MergeSort(int[] arr,int low,int high){
        if(low<high){
            int mid=(high+low)/2;
            MergeSort(arr,low,mid);
            MergeSort(arr,mid+1,high);
            //先递归，后排序；从后往前执行程序
            merge(arr,low,mid,high);
        }
    }
    public static void merge(int[] arr,int low,int mid,int high){
        int[] temp=new int[high-low+1];
        int i=low;int j=mid+1;
        int k=0;
        while(i<=mid&&j<=high){    //两指针指向前后数组，将小的填入辅助数组
            if(arr[i]<arr[j]){
                temp[k++]=arr[i++];
            }else{
                temp[k++]=arr[j++];
            }
        }
        //当low中的数组和mid+1中的数组比较时，会出现一个剩余的数
        while(i<=mid){    //剩余数在low中
            temp[k++]=arr[i++];
        }
        while(j<=high){   //剩余数在mid+1中
            temp[k++]=arr[j++];
        }
        for(int t=0;t<temp.length;t++){
            arr[low++]=temp[t];
        }

    }
    public static void main(String[] args) {
        int[] arr={1,9,2,5,7,3,5,6,8};
        MergeSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}