import java.util.Arrays;
/**
 * @Auther: dzy
 * @Date: 2022/2/27 14:50
 * @Description: 归并排序加强
 * 1、通过在调用归并函数前判断a[mid]和a[mid+1]的大小决定是否需要归并，这样减少了一定的比较时间
 * 2、通过每次调用sort排序函数，每次递归原数组和辅助数组轮换，轮流作为辅助数组，就是比如:先将排序好的放在辅助数组
 * 然后下一次递归中以辅助数组为原数组将其归并后放在src[]中,不断替换;注意:最上层递归中归并后是将aux中的元素排序后放在src中，
 * 递归的层数有奇有偶这是不确定的，但是最终排序结果总是放在src中
 */
public class MergeEn {

    private MergeEn(){}

    public static void sort(Comparable[] a){
        Comparable[] aux = a.clone();    //创建数组a的副本
        sort(a, aux, 0, a.length-1);
    }
    //归并排序函数
    private static void sort(Comparable[] src, Comparable[] aux, int low, int hi){
        //递归结束条件，大小为1结束递归
        if(low >= hi) return ;
        int mid = low + (hi - low) / 2;
        //将左右两边分别排序
        sort(aux, src, low, mid);
        sort(aux, src, mid + 1, hi);
        //排序后调用归并方法
        if (less(aux[mid], aux[mid + 1])) {
            //左半边最大值小于右半边最小值说明已经不需要归并，直接将数组内元素复制到src[]中,第一个是原来的
            System.arraycopy(aux, low, src, low, hi - low + 1);
            return ;
        }
        merge(src, aux, low, mid, hi);
    }
    /*
     * @Description:  归并两个有序数组
     * @Param: [a, aux, low, hi]
     * @return: void
     * @Author: dzy
     * @Date: 2022/2/27
     */
    private static void merge(Comparable[] src, Comparable[] des, int low, int mid, int hi){
        assert isSorted(src, low, mid);
        assert isSorted(src, mid+1, hi);
        int i = low;
        int j = mid + 1;
        for (int k = low; k <= hi; k++)
        {
            if (i > mid) src[k] = des[j++];
            else if (j > hi) src[k] = des[i++];
            else if (less(src[i], des[j])) src[k] = des[i++];
            else src[k] = des[j++];
        }
        assert isSorted(src, low, hi);

    }

    private static boolean less(Comparable a, Comparable b){return a.compareTo(b)<0;}
    private static boolean isSorted(Comparable[] a){
        return isSorted(a, 0, a.length-1);
    }
    private static boolean isSorted(Comparable[] a, int low, int hi){
        for(int i = low; i < hi; i++){
            if (less(a[i+1],a[i])) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Comparable[] a = new Comparable[]{3,2,6,4,7,5};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}