归并排序优化 - 图1

优化 1：在小区间里使用插入排序

如果区间里只有 2 个元素，例如 [4,3]，只要把它们直接交换一下位置就可以了。但是这种情况还太特殊，对于区间里有 3 个元素、4 个元素的情况就不奏效了，一个更直接且有效的做法是：在小区间里使用插入排序

事实上，在归并排序的子过程里，可以使用插入排序的原因是：

  1. 首先，操作的指令数更少
  2. 其次，插入排序也是稳定的排序算法，修改成插入排序并不影响归并排序的稳定性

当然这个子区间不能很大，子区间在多长的时候转而使用插入排序，这需要通过实验才能知道。学习过机器学习的朋友，就会知道它是一个超参数，目前 Java 语言的库函数将它定义成 47

优化 2：子区间本身有序则无需归并

如果这个子区间本身就是有序的，我们没有必要执行归并的过程。

例如：[1, 3, 4, 5, 6, 7, 8, 9]。 在上一节介绍的分治算法的时候，需要将它一分为二，前半部分是 [1, 3, 4, 5]，后半部分是 [6, 7, 8, 9]，事实上这一步是没有必要的。

优化 3：在整个归并的过程中，使用同一个辅助数组

上一节的做法，我们每次归并之前都得创建一个临时数组，在 Java 语言中，使用完以后就会被垃圾回收机制回收。

这个频繁创建数组和销毁数组的过程，有一定性能消耗；
不管是复制数组，还是把归并的结果赋值回去，都得计算偏移量。
而事实上，当我们全局使用一个临时数组用于归并的时候，可以省略偏移量的计算。
下面我们就从代码层面讲解如何优化归并排序。

代码编写

优化 1：在小区间里使用插入排序

为此，我们还要写一个在指定区间进行插入排序的私有函数。

  1. /**
  2.  * 列表大小等于或小于该大小，将优先于 mergesort 使用插入排序
  3.  */
  4. const INSERTION_SORT_THRESHOLD = 47;
  6. if (right - left <= INSERTION_SORT_THRESHOLD) {
  7.     insertionSort(arr, left, right);
  8.     return;
  9. }
  12. /**
  13.  * 对数组给定的部分使用插入排序
  14.  *
  15.  * @param arr   给定数组
  16.  * @param left  左边界，能取到
  17.  * @param right 右边界，能取到
  18.  */
  19. const insertionSort = (arr, left, right) => {
  20.   for (int i = left + 1; i <= right; i++) {
  21.     let temp = arr[i];
  22.     let j = i;
  23.     while (j > left && arr[j - 1] > temp) {
  24.       arr[j] = arr[j - 1];
  25.       j--;
  26.     }
  27.     arr[j] = temp;
  28.   }
  29. }

优化 2：子区间本身有序就无需归并

在代码上，我们只要判断第 1 部分的最后一个元素是不是大于第 2 部分的第 1 个元素即可。

  1. if (arr[mid] <= arr[mid + 1]) {
  2.     return;
  3. }

注意：这里可以取等号。

优化 3：在整个归并的过程中，使用同一个辅助数组

  1. /**
  2.  * 列表大小等于或小于该大小，将优先于 mergesort 使用插入排序
  3.  */
  4. // threshold 门槛
  5. const INSERTION_SORT_THRESHOLD = 47;
  8. /**
  9.  * 对数组给定的部分使用插入排序
  10.  *
  11.  * @param arr   给定数组
  12.  * @param left  左边界，能取到
  13.  * @param right 右边界，能取到
  14.  */
  15. const insertionSort = (arr, left, right) => {
  16.   for (let i = left + 1; i <= right; i++) {
  17.     let temp = arr[i];
  18.     let j = i;
  19.     while (j > left && arr[j - 1] > temp) {
  20.       arr[j] = arr[j - 1];
  21.       j--;
  22.     }
  23.     arr[j] = temp;
  24.   }
  25. }
  27. const mergeOfTwoSortedArray = (nums, left, mid, right, temp) => {
  28.   // 原数组拷贝
  29.   for (let i = left; i <= right; i++) {
  30.     temp[i] = nums[i];
  31.   }
  33.   let i = left;
  34.   let j = mid + 1;
  35.   for (let k = left; k <= right; k++) {
  36.     if (i == mid + 1) {
  37.       nums[k] = temp[j];
  38.       j++;
  39.     } 
  40.     else if (j == right + 1) {
  41.       nums[k] = temp[i];
  42.       i++;
  43.     } 
  44.     else if (temp[i] <= temp[j]) {
  45.       // 注意：这里一定要写成 <=，否则就变成了非稳定排序
  46.       nums[k] = temp[i];
  47.       i++;
  48.     } 
  49.     else {
  50.       nums[k] = temp[j];
  51.       j++;
  52.     }
  53.   }
  54. }
  56. // 归并排序的拆分部分
  57. const mergeSort = (nums, left, right, temp) => {
  58.   // 优化 1：小区间使用插入排序
  59.   if (right - left <= INSERTION_SORT_THRESHOLD) {
  60.     insertionSort(nums, left, right);
  61.     return;
  62.   }
  63.   const mid = (left + right)>>>1;
  64.   mergeSort(nums, left, mid, temp);
  65.   mergeSort(nums, mid + 1, right, temp);
  67.   // 优化 2：数组已经有序的情况下，不再合并
  68.   if (nums[mid] <= nums[mid + 1]) {
  69.     return;
  70.   }
  71.   mergeOfTwoSortedArray(nums, left, mid, right, temp);
  72. }
  74. // 排序
  75. const sortArray = (nums) => {
  76.   let len = nums.length;
  78.   // 优化 3：全局使用一份临时数组
  79.   let temp = new Array(len);
  80.   mergeSort(nums, 0, len - 1, temp);
  81.   return nums;
  82. }

}
练习
（必做）「力扣」《剑指 Offer》第 51 题：数组中的逆序对；
说明：这是一道非常经典的使用「归并排序」或者说「分治思想」的例题，请一定要花时间弄清楚。

（选做）「力扣」第 315 题：计算右侧小于当前元素的个数。
说明：这里需要用到「索引数组」的技巧，「索引数组」其实就是在原始数组的基础上包装了一层，使得程序在操作的时候知道操作的数在原始输入数组里的下标。刚开始在理解上可能会很绕，但是思想其实是很简单的。如果很生硬地去想觉得很难理解，建议在草稿纸上写写画画。

归并排序就为大家介绍到这里了，这个时候，相信大家已经感觉到，即使是非常简单的排序任务，也有许多细节要考虑。下一节将要为大家介绍快速排序算法，我们下节再见。

作者：liweiwei1419
链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/55gb35/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。