关键点：

    • 对于长度小于 7 的数组使用插入排序效率更高。
    • 使用临时数组 int[] temp = new int[len] 。

    • 每次进行区域内的排序时使用函数 System.arraycopy(nums, left, temp, left, right - left + 1); ，参数分别表示为被复制的数组、被复制的起点下标、目标数组、目标数组起点下标、复制长度。

      1. public class MergeSort {
      2.   final static int THRESHOLD = 7;
      4.   public static void sort(int[] nums) {
      5.       int len = nums.length;
      6.       int[] temp = new int[len];
      7.       mergeSort(nums, 0, len - 1, temp);
      8.   }
      10.   private static void mergeSort(int[] nums, int left, int right, int[] temp) {
      11.       if (right - left + 1 <= THRESHOLD) {
      12.           selectionSort(nums, left, right);
      13.           return;
      14.       }
      16.       int mid = left + (right - left) / 2;
      17.       mergeSort(nums, left, mid, temp);
      18.       mergeSort(nums, mid + 1, right, temp);
      19.       if (nums[mid] <= nums[mid + 1]) {
      20.           return;
      21.       }
      22.       mergeTwoList(nums, left, mid, right, temp);
      23.   }
      25.   private static void mergeTwoList(int[] nums, int left, int mid, int right, int[] temp) {
      26.       System.arraycopy(nums, left, temp, left, right - left + 1);
      27.       int i = left;
      28.       int j = mid + 1;
      30.       for (int k = left; k <= right; k++) {
      31.           if (i == mid + 1) {
      32.               nums[k] = temp[j];
      33.               j++;
      34.           } else if (j == right + 1) {
      35.               nums[k] = temp[i];
      36.               i++;
      37.           } else if (temp[i] <= temp[j]) {
      38.               nums[k] = temp[i];
      39.               i++;
      40.           } else {
      41.               nums[k] = temp[j];
      42.               j++;
      43.           }
      44.       }
      45.   }
      47.   private static void selectionSort(int[] nums, int left, int right) {
      48.       for (int i = left + 1; i <= right; i++) {
      49.           int temp = nums[i];
      50.           int j = i;
      52.           while (j > left && nums[j - 1] > temp) {
      53.               nums[j] = nums[j - 1];
      54.               j--;
      55.           }
      56.           nums[j] = temp;
      57.       }
      58.   }
      59. }