基本思想

归并排序的基本思想是，将需要排序的数列分割成两份，直到分割到长度为1时，然后再对这些数列进行两两合并，在合并过程中对数组进行排序。他可以分成以下三个步骤：

  • 分解（Divide）： 将n的数组分成 n/2 的两个子数组。
  • 治理（Conquer）: 按照一定规则合并两个子数组，检查两个数组首位的数字哪个小，将小的数字推入新的数组中，直到两个子数组的数字都被处理完。
  • 合并（Merge）：按照规则依次将所有的数组合并完成，最终得到排序完成的数组。

具体的合并过程可以见下图，我们先将这个 [14, 12, 15, 13, 11, 16] 的数组进行切分，切分到最小单位后，再进行合并，最终得到排序完成的数组。
image.png

代码实现

  1. /**
  2.  * @param {原数组} arr
  3.  */
  4. export default function mergeSort(arr, l, r) {
  5.   if (l === r) {
  6.     return [arr[l]]
  7.   }
  8.   const result = []
  9.   const mid = Math.floor((r + l - 1) / 2)
  10.   const left = mergeSort(arr, l, mid)
  11.   const right = mergeSort(arr, mid + 1, r)
  12.   let i = 0
  13.   let j = 0
  14.   while (i < left.length || j < right.length) {
  15.     if (i >= left.length || left[i] >= right[j]) {
  16.       result.push(right[j]);
  17.       j++;
  18.     } else if (j >= right.length || left[i] <= right[j]) {
  19.       result.push(left[i]);
  20.       i++;
  21.     }
  22.   }
  23.   return result
  24. }

归并排序的时间复杂度是n log(n) 。因为归并排序每次都将数组平均分成两份，所以拆分后的高度是稳定的log(n) ， 拆分完成后我们每次去合并的复杂度是N，因此最终的复杂度是n log(n)。

归并排序vs快速排序

  1. 归并排序是稳定的n*log(n) 的排序方式，最差和最好的复杂度是一样的。但是快排并不是稳定的排序方式，这是因为我们在快排中，选取的divider可能并不是处于数组中间的位置。如果运气不佳，我们在进行快排时，选取的divider排序好恰好是靠左的数字，那么切分后树的高度就是n，最差的时间复杂度是 n^2。
  2. 归并排序在每次排序时要创建新的数组，因此空间复杂度O(n)要比快排O(1)更高, 快排直接对原数组进行排序，属于原地排序。