归并排序（优化）

归并排序的算法思想：递归的将待排序大数组一分为二，直至不可再分，即分割后的小数组只有一个待排序元素为止。此时使用合并算法思想，对已经有序的数组进行合并，合并为一个大数组。不断重复合并过程，直至所有小数组合并为一个数组为止。

归并排序的时间复杂度是：O($N \log_{}N$)。假如有待排序大数组有 8 个元素，那么只需要分割 $\log_{2}8=3$ 次，就可以达到不可再分的状态。然后每一步都需要 O(N) 的复杂度来合并。因此总的时间复杂度是 O($N \log_{}N$)。

public class MergeSort {
    // 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并，注意前后都是闭区间
    private static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // 初始化，i 指向左半部分的起始索引位置 l；j 指向右半部分起始索引位置 mid+1
        int i = l, j = mid + 1;

        for (int k = l; k <= r; k++) {
            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // 递归的调用归并排序，对 arr[l...r] 的范围进行排序
    private static void sort(Comparable[] arr, int l, int r) {
        // 优化: 对于小规模数组, 使用插入排序
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }

        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);

        // 优化: 对于 arr[mid] <= arr[mid+1] 的情况，不进行 merge
        // ---
        // 因为，通过上面递归的对左、右部分分别排序后，左半部分的最后一个元素，即 arr[mid]，一定是左半部分中最大的
        // 同理，右半部分的第一个元素，即 arr[mid+1]，一定是右半部分中最小的。因此如果 arr[mid] <= arr[mid+1]，
        // 则说明，当前 sort 递归子函数处理的数据范围已经是排好序的了，因此可以不用再进行一次 merge
        // ---
        // 对于近乎有序的数组非常有效，但是对于一般情况，有一定的性能损失。因为每次都会调用 if
        // 所以，如果你知道你的待排序数据近乎有序，那可以加上这条优化，否则去掉这个 if 判断就好
        if (arr[mid].compareTo(arr[mid + 1]) > 0)
            merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr) {
        int n = arr.length;

        sort(arr, 0, n - 1);
    }
}