归并排序
​​​​​​
要将一个数组排序，可以先递归将它分成两半分别排序，然后将结果归并起来。
 归并性质：任意长度为N的数组排序所需的时间和Nlog（N)成正比；缺点则是它所需要的额外空间和N成正比。

实现一：自顶向下（递归，分治）

private static Comparable[] aux;//归并所需要的辅助数组
    public static void main(String[] args){
        String[] string = {"E", "E", "G", "M", "R", "A", "C", "E", "R", "T"};
        show(string);
        mergeSort(string);
        System.out.println(isSorted(string));
        show(string);
    }

    public static void mergeSort(Comparable[] array){
        aux = new Comparable[array.length];//一次性分配空间
        sort(array, 0, array.length - 1);
    }
    public static void sort(Comparable[] array, int low, int hight){
        //将数组a[low..hi]排序
        if(hight <= low)
            return;
        int mid = low + (hight - low) / 2;
        sort(array, low, mid);//将左边排序
        sort(array, mid + 1, hight);//将右边排序
        merge(array, low, mid, hight);//归并结果
    }
    //原地归并的抽象方法
    public static void merge(Comparable[] array, int low, int mid, int hight){
        //将a[lo..mid]和a[mid + 1...hi]归并
        int left = low;//左边开始
        int right = mid + 1;//右边开始
        for(int k = low; k <= hight; k++){//将a[low..hight]复制到aux[low...hight]
            aux[k] = array[k];
        }
        for (int k = low; k <= hight; k++){//归并回到a[low...hight]中
            if( left > mid){//左半边元素用完（取右半边的元素）
                array[k] = aux[right++];
            }else if(right > hight){//右半边元素已经全部用完（取左半边的元素）
                array[k] = aux[left++];
            }else if(less(aux[right],aux[left])){//右半边的当前元素小于左半边的当前元素（取右半边的元素
                array[k] = aux[right++];
            }else{//右半边的当前元素大于等于左半边的当前元素（取左半边元素）
                array[k] = aux[left++];
            }

        }
    }



    //比较函数，v小于w就返回真
    public static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    //交换函数
    public static void exch(Comparable[] array, int i, int j){
        Comparable temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    //打印函数
    public static void show(Comparable[] array){
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] +" ");
        }
        System.out.println();
    }
    //测试元素是否有序
    @Contract(pure = true)
    public static boolean isSorted(Comparable[] a) {
        //测试元素是否有序
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

实现二：自底向上实现

private static Comparable[] aux;//归并所需要的辅助函数
    public static void main(String[] args){
        String[] string = {"E", "E", "G", "M", "R", "A", "C", "E", "R", "T"};
        show(string);
        sort(string);
        System.out.println(isSorted(string));
        show(string);
    }
    public static void sort(Comparable[] array){
        //进行lgN次两两归并
        int length = array.length;
        aux = new Comparable[length];
        for(int sz = 1; sz < length; sz += sz){//sz子数组大小
            for(int low = 0; low < length - sz; low += sz + sz){//low子数组索引
                merge(array, low, low + sz - 1, Math.min(low + sz + sz - 1, length - 1));

            }

        }

    }

    private static void merge(Comparable[] array, int low, int mid, int hight) {
        int left = low;
        int right = mid + 1;
        //将array复制到aux中
        for(int k = low; k <= hight; k++){
            aux[k] = array[k];
        }
        for(int k = low; k <= hight; k++){
            if(left > mid){//左边元素用尽，取右边元素
                array[k] = aux[right++];

            }else if(right > hight){//右边元素用尽，取左边元素
                array[k] = aux[left++];

            }else if(less(aux[right],aux[left])){//当前右边元素小于当前左边元素，取右边元素
                array[k] = aux[right++];

            }else{
                array[k] = aux[left++];
            }

        }
    }
    //比较函数，v小于w就返回真
    public static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    //交换函数
    public static void exch(Comparable[] array, int i, int j){
        Comparable temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    //打印函数
    public static void show(Comparable[] array){
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] +" ");
        }
        System.out.println();
    }
    //测试元素是否有序
    public static boolean isSorted(Comparable[] a) {
        //测试元素是否有序
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }