归并排序就是对数组的左半边和右半边别离排序，而后再合并两个有序数组。
- 归并排序的过程能够在逻辑上形象成一棵二叉树，树上的每个节点的值能够认为是
nums[lo..hi]，叶子节点的值就是数组中的单个元素 - 而后，在每个节点的后序地位（左右子节点曾经被排好序）的时候执行
merge函数，合并两个子节点上的子数组 - 这个
merge操作会在二叉树的每个节点上都执行一遍，执行程序是二叉树后序遍历的程序
一句话总结，归并排序实际上就是先对数组一直进行二分，分到只有一个元素为止，此时 merge 办法开始发挥作用，将两个元素为一组，合并为长度为 2 的有序数组，再将两个长度为 2 的有序数组为一组，合并为长度为 4 的有序数组，以此类推class Merge { // 用于辅助合并有序数组（不能原地合并，须要借助额定空间） private static int[] temp; public static void sort(int[] nums) { // 防止递归中频繁调配和开释内存可能产生的性能问题 // 提前给辅助数组开拓内存空间 temp = new int[nums.length]; // 原地批改的形式对整个数组进行排序 sort(nums, 0, nums.length - 1); } // 定义：将子数组 nums[lo..hi] 进行排序 private static void sort(int[] nums, int lo, int hi) { if (lo == hi) { // 单个元素不必排序 return; } // 这样写是为了避免溢出，成果等同于 (hi + lo) / 2 // 留神：对于无奈整除的状况，Java 中 int 类型会主动向下取整 int mid = lo + (hi - lo) / 2; // 先对左半局部数组 nums[lo..mid] 排序 sort(nums, lo, mid); // 再对右半局部数组 nums[mid+1..hi] 排序 sort(nums, mid + 1, hi); // 将两局部有序数组合并成一个有序数组 merge(nums, lo, mid, hi); } // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组 private static void merge(int[] nums, int lo, int mid, int hi) { // 先把 nums[lo..hi] 复制到辅助数组中 // 以便合并后的后果可能间接存入 nums for (int i = lo; i <= hi; i++) { temp[i] = nums[i]; } // 数组双指针技巧，合并两个有序数组 // i => 左半边数组起始下标 // j => 右半边数组起始下标 int i = lo, j = mid + 1; for (int p = lo; p <= hi; p++) { if (i == mid + 1) { // 左半边数组已全副被合并，只需把右半边数组合并过去即可 nums[p] = temp[j++]; } else if (j == hi + 1) { // 右半边数组已全副被合并，只需把左半边数组合并过去即可 nums[p] = temp[i++]; } else if (temp[i] > temp[j]) { // 将较小的元素合入，同时下标后退一位，此时是升序 // 只有将 > 改为 < 就能够把后果改为降序 nums[p] = temp[j++]; } else { nums[p] = temp[i++]; } } }}归并排序工夫复杂度为 O(nlogn)