归并排序就是先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并。

    1. // 定义：排序 nums[lo..hi]
    2. void sort(int[] nums, int lo, int hi) {
    3.     if (lo == hi) {
    4.         return;
    5.     }
    6.     int mid = (lo + hi) / 2;
    7.     // 利用定义，排序 nums[lo..mid]
    8.     sort(nums, lo, mid);
    9.     // 利用定义，排序 nums[mid+1..hi]
    10.     sort(nums, mid + 1, hi);
    12.     /****** 后序位置 ******/
    13.     // 此时两部分子数组已经被排好序
    14.     // 合并两个有序数组，使 nums[lo..hi] 有序
    15.     merge(nums, lo, mid, hi);
    16.     /*********************/
    17. }
    19. // 将有序数组 nums[lo..mid] 和有序数组 nums[mid+1..hi]
    20. // 合并为有序数组 nums[lo..hi]
    21. void merge(int[] nums, int lo, int mid, int hi);
    1. class Merge {
    3.     // 用于辅助合并有序数组
    4.     private static int[] temp;
    6.     public static void sort(int[] nums) {
    7.         // 先给辅助数组开辟内存空间
    8.         temp = new int[nums.length];
    9.         // 排序整个数组（原地修改）
    10.         sort(nums, 0, nums.length - 1);
    11.     }
    13.     // 定义：将子数组 nums[lo..hi] 进行排序
    14.     private static void sort(int[] nums, int lo, int hi) {
    15.         if (lo == hi) {
    16.             // 单个元素不用排序
    17.             return;
    18.         }
    19.         // 这样写是为了防止溢出，效果等同于 (hi + lo) / 2
    20.         int mid = lo + (hi - lo) / 2;
    21.         // 先对左半部分数组 nums[lo..mid] 排序
    22.         sort(nums, lo, mid);
    23.         // 再对右半部分数组 nums[mid+1..hi] 排序
    24.         sort(nums, mid + 1, hi);
    25.         // 将两部分有序数组合并成一个有序数组
    26.         merge(nums, lo, mid, hi);
    27.     }
    29.     // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    30.     private static void merge(int[] nums, int lo, int mid, int hi) {
    31.         // 先把 nums[lo..hi] 复制到辅助数组中
    32.         // 以便合并后的结果能够直接存入 nums
    33.         for (int i = lo; i <= hi; i++) {
    34.             temp[i] = nums[i];
    35.         }
    37.         // 数组双指针技巧，合并两个有序数组
    38.         int i = lo, j = mid + 1;
    39.         for (int p = lo; p <= hi; p++) {
    40.             if (i == mid + 1) {
    41.                 // 左半边数组已全部被合并
    42.                 nums[p] = temp[j++];
    43.             } else if (j == hi + 1) {
    44.                 // 右半边数组已全部被合并
    45.                 nums[p] = temp[i++];
    46.             } else if (temp[i] > temp[j]) {
    47.                 nums[p] = temp[j++];
    48.             } else {
    49.                 nums[p] = temp[i++];
    50.             }
    51.         }
    52.     }
    53. }