public class Merge {
    //初始化辅助数组
    private static Comparable[] assist;

    //判断数字大小,true ab ;
    private static boolean less(Comparable a,Comparable b){
        return a.compareTo(b)<0;
    }

    //对数组进行排序
    public static void sort(Comparable[] a){
        //初始化assist数组
        assist = new Comparable[a.length];
        //建立最小索引和最大索引
        int begin = 0;
        int end = a.length-1;
        //调用sort重载方法完成数组a中索引begin到end中的排序
        sort(a,begin,end);
    }

    //开始将数组中begin到end进行排序
    private static void sort(Comparable[] a,int begin,int end){
        //做安全性校验
        if(begin>=end){
            return;
        }
        //对begin到end的数据进行分组
        int mid = begin + (end - begin) / 2;
        //对两边的数组进行排序
        sort(a,begin,mid);
        sort(a,mid+1,end);
        //接下来对两组数据进行归并即可
        merge(a,begin,mid,end);
    }


    //a数组中begin到mid为一组，mid+1到end为一组，将两组进行归并
    private static void merge(Comparable[] a,int begin,int mid,int end){
        //定义三个指针
        int i=begin;
        int p1=begin;
        int p2=mid+1;
        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的哪个，放到辅助数组的对应索引处
        while(p1<=mid && p2<=end){
            //比较索引处的值
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else{
                assist[i++] = a[p2++];
            }
        }

        //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数据的对应索引处
        while(p1<=mid){
            assist[i++]=a[p1++];
        }

        //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数据的对应索引处
        while(p2<=end){
            assist[i++]=a[p2++];
        }

        //把辅助数组中的元素拷贝到原数组中
        for(int index=begin;index<=end;index++){
            a[index] = assist[index];
        }
    }
}