归并排序

维护左右两部分分别有序，然后使用merge函数合并为整体有序，需要借助辅助数组空间。

算法复杂度：O(nlogn):相当于分成log n层的二叉树，每层复杂度为O(n)

归并算法中，要点，merge算法步骤（if有四个分支）
1、先算两边是否处理完毕，如左边处理完毕处理右边（看左右的索引值是否超过边界）
2、然后比较两边大小，用小的值赋值到对应位置，对应位置的索引加加

优化点
1、排序后，左边最大值比右边最小值要小，不进行归并（arr[mid].compareTo(arr[mid+1])<0）,如果是有序数组，相当于每个叶子节段内部是常量操作O(1)，叶子结点个数为复杂度，即为O(n)
2、递归后，小于一定值，使用插入排序（不确定起作用，和编译器环境有关）
3、归并算法每次都生成数组，可以在外面生成大数组，然后复用大数组，不用每次New

import java.util.Arrays;

/**
 * 归并排序
 * O(nlogn):相当于分成log n层的二叉树，每层复杂度为O(n)
 * 优化点
 * 1、排序后，左边最大值比右边最小值要小，不进行归并（arr[mid].compareTo(arr[mid+1])<0）,
 *      如果是有序数组，相当于每个叶子节段内部是常量操作O(1)，叶子结点个数为复杂度，即为O(n)
 * 2、递归后，小于一定值，使用插入排序（不确定起作用，和编译器环境有关）
 * 3、归并算法每次都生成数组，可以在外面生成大数组，然后复用大数组，不用每次New
 *      E[] arrTemp = Arrays.copyOf(arr,arr.length);
 *      System.arraycopy(arr,l,tempArr,l,r-l+1);
 *
 * 归并算法中，要点，merge算法步骤（if有四个分支）
 * 1、先算两边是否处理完毕，如左边处理完毕处理右边（看左右的索引值是否超过边界）
 * 2、然后比较两边大小，用小的值赋值到对应位置，对应位置的索引加加
 */
public class MergeSort {
    public static <E extends Comparable<E>> void sort(E[] arr) {
        if (arr == null) {
            return;
        }
        sort(arr,0, arr.length-1);
//        merge(arr,0, arr.length/2, arr.length-1);
    }

    // 区间为前闭后闭
    private static <E extends Comparable<E>> void sort(E[] arr,int l,int r){
        if (l>=r) {
            return;
        }

        // 优化点
        // 因merge和sort内部 操作较多（复杂度的常量），
        // 在数组长度比较小的情况，不如简单的插入排序
        // java有效（该优化牵扯方法切换，可能在其他脚本语言会更耗时，暂注释掉）
//        if (r-l<=15) {
//            InsertionSort.sort2(arr,l,r);
//            return;
//        }
        // 分成前后两段
        int mid = (l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);

        // 优化点
        // 1、如果是有序队列，可以使算法复杂度变为O(n)
        // 2、因为内部循环不执行，相当于只执行递归，复杂度计算，相当于求二叉树的节点数
        // 从底向上加为 (1/2+1/4+1/8+...)*n ≈ O(n)
        ///3、参考插入排序法遇到有序数组情况，也为O(n)
        if (arr[mid].compareTo(arr[mid+1])>0) {
            merge(arr, l, mid, r); // 两段有序数组排序
        }
    }

    // merge原则：左边（有序） 和 右边（有序） 比较 ，小的放入数组第K个元素
    private static <E extends Comparable<E>> void merge(E[] arr,int l,int mid,int r) {
        E[] tempArr = Arrays.copyOfRange(arr, l, r + 1);
        int i=l,j=mid+1; // 左右两边的下标，和 主Arr 相差 l；
        for (int k = l; k <= r; k++) {
            if (i>mid) { // 左边已经添加完毕，只操作右边
                arr[k] = tempArr[j-l];
                j++;
            } else if (j>r) { // 右边已经添加完毕，只操作左边
                arr[k] = tempArr[i-l];
                i++;
            } else if (tempArr[i-l].compareTo(tempArr[j-l])<0) { // 比较 左右 两边 哪个小
                arr[k] = tempArr[i-l];
                i++;
            } else {
                arr[k] = tempArr[j-l];
                j++;
            }
        }
    }
}

优化

import java.util.Arrays;

public class MergeSort {

    // 优化 使用外部数组，减少声明空间次数
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        if (arr == null) {
            return;
        }
        E[] arrTemp = Arrays.copyOf(arr,arr.length);
        sort2(arr,0, arr.length-1,arrTemp);
//        merge(arr,0, arr.length/2, arr.length-1);
    }

    // 区间为前闭后闭
    private static <E extends Comparable<E>> void sort2(E[] arr,int l,int r,E[] arrTemp){
        if (l>=r) {
            return;
        }

        // 优化点
        // 因merge和sort内部 操作较多（复杂度的常量），
        // 在数组长度比较小的情况，不如简单的插入排序
        // java有效（该优化牵扯方法切换，可能在其他脚本语言会更耗时，暂注释掉）
//        if (r-l<=15) {
//            InsertionSort.sort2(arr,l,r);
//            return;
//        }
        // 分成前后两段
        int mid = (l+r)/2;
        sort2(arr,l,mid,arrTemp);
        sort2(arr,mid+1,r,arrTemp);

        // 优化点
        // 1、如果是有序队列，可以使算法复杂度变为O(n)
        // 2、因为内部循环不执行，相当于只执行递归，复杂度计算，相当于求二叉树的节点数
        // 从底向上加为 (1/2+1/4+1/8+...)*n ≈ O(n)
        ///3、参考插入排序法遇到有序数组情况，也为O(n)
        if (arr[mid].compareTo(arr[mid+1])>0) {
            merge2(arr, l, mid, r,arrTemp); // 两段有序数组排序
        }
    }

    // merge原则：左边（有序） 和 右边（有序） 比较 ，小的放入数组第K个元素
    private static <E extends Comparable<E>> void merge2(E[] arr,int l,int mid,int r,E[] tempArr) {
        //E[] tempArr = Arrays.copyOfRange(arr, l, r + 1);
        System.arraycopy(arr,l,tempArr,l,r-l+1);
        int i=l,j=mid+1; // 左右两边的下标，和 主Arr 相差 l；
        for (int k = l; k <= r; k++) {
            if (i>mid) {
                arr[k] = tempArr[j];
                j++;
            } else if (j>r) {
                arr[k] = tempArr[i];
                i++;
            } else if (tempArr[i].compareTo(tempArr[j])<0) { // 比较 左右 两边 哪个小
                arr[k] = tempArr[i];
                i++;
            } else {
                arr[k] = tempArr[j];
                j++;
            }
        }
    }
}