Java版归并排序 演示代码（带注释）

Code：

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {
    /**
     * 私有化
     */
    private MergeSort() {}

    /**
     * 归并排序的sort方法
     * @param arr 待排序数组
     * @param <E> 可比较的元素
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 内部sort方法
     * @param arr 待排序数组
     * @param l 左边界索引
     * @param r 右边界索引
     * @param <E> 元素类型（必须可比较）
     */
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        // 递归终止条件
        if (l >= r) {
            return;
        }
        // 分为两部分，取其中间索引（分治）
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // 将排好序的两部分合二为一（合并）
        merge(arr, l, mid, r);
    }

    /**
     * 合并两个有序的区间 arr[l, mid] 和 arr[mid+1, r]
     * @param arr 待排序数组（整个数组或部分）
     * @param l 数组索引的左边界
     * @param mid 数组的中间索引
     * @param r 数组索引的右边界
     * @param <E> 元素类型
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        // 备份数组的[l, r]区间
        E[] tmp = Arrays.copyOfRange(arr, l, r + 1);

        // 指针i，指向左半部的开头
        int i = l;
        // 指针j，指向右半部的开头
        int j = mid + 1;

        // 为[l, r]区间的arr排序
        for (int k = l; k <= r; k++) {
            // 如果i指针移动到了mid之外（右）
            // 则说明数组左侧部分已经全部遍历过了
            if (i > mid) {
                arr[k] = tmp[j - l];
                j++;
            }
            // 如果j指针也移动出了r边界
            // 则数组左侧部分已经完成遍历，这时处理左数组即可
            else if (j > r) {
                arr[k] = tmp[i - l];
                i++;
            }
            // 如果i指针在左半边数组的索引范围内
            // 且j指针也在右半边数组的索引范围之内
            // 则比较i,j两索引上的元素大小
            else if (tmp[i - l].compareTo(tmp[j - l]) <= 0) {
                // tmp[i] <= tmp[j]
                arr[k] = tmp[i - l];
                i++;
            }
            // 剩下的一种情况，i,j均未越界，且tmp[i] > tmp[j]
            else {
                arr[k] = tmp[j - l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {9, -1, 5, 8, 2, 17, 7, 0, 6};
        MergeSort.sort(arr);
        for (int item : arr) {
            System.out.println(item);
        }
    }
}