public class Merge {
    public static void sort(Comparable[] a){//排序方法,传入一个数组a,再调用一个可以把数组拆成两部分再分别排序再归并的方法           
        sort(a,0,a.length-1);
    }
    
    private static void sort(Comparable[] a, int lo, int hi) { //传入开始角标和结束角标
        if(lo >= hi)    //当开始角标已经走到了结束角标或者已经超过了结束角标了,证明已经把一个数组全都拆分完了
            return;     //没定义出口,会导致栈溢出,stackoverflowerror
        int mid = lo+(hi-lo)/2;//定义这个数组的中间角标,然后递归
        sort(a,lo,mid);         //将左半边数组排序
        sort(a,mid+1,hi);       //将右半边数组排序
        merge(a,lo,mid,hi);     //将这两个数组合在一起
        
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo,j=mid+1;                         //先把两个数组的开始角标存在一个变量里
        Comparable[] aux = new Comparable[a.length];//实例化一个辅助数组
        //如果for循环的判断条件有误,会导致越界异常ArrayIndexOutOfBoundsException
        for(int k =lo;k<=hi;k++){   //将原数组的元素复制到辅助数组里面
            aux[k] = a[k];          //因为hi代表的是角标,所以要加等于号,长度就不用
        }
        for(int k =lo;k<=hi;k++){ //因为有lo~hi个元素,所以这个循环的条件就是k<=hi,有多少个元素就执行多少次,每次放进一个元素
            if(i>mid)               //两个数组合并,左数组的开始角标为i,右数组的开始角标为j,当坐数组开始角标i已经走到了它数组的最后一角标之后,证明已经全部元素都出去,没了,
                a[k] = aux[j++];    //那就将右数组的元素都依次存进a数组中
            else if(j>hi)           //同理,当右数组的开始角标已经走到最末尾了,右数组里没有元素了可以和左数组作比较了,那么就将左数组的元素一个一个存进a数组中
                a[k] = aux[i++];
            else if(less(aux[i],aux[j]))    //当这两个数组都还没走到数组末尾,则比较这两个数组的大小,如果aux[i]的值比aux[j]的值小,
                a[k] = aux[i++];            //则将aux[i]的值存进a数组里面,并且i角标++
            else 
                a[k] = aux[j++];            //如果aux[i]的值不比aux[j]的值小,那么将aux[j]的值存进a数组,并且j角标要自增1
        }
        
    }

    private static boolean less(Comparable v, Comparable w) {
        
        return v.compareTo(w)<0;
    }

    public static void main(String[] args) {
        Integer[] a = new Integer[]{999,494,110,12,154,123,456,356,486,576,16,654,23,451,};
        sort(a);
        for(int num : a){
            System.out.print(" "+num);
        }

    }

}