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);
}
}
}