4. 归并排序

算法描述

归并排序使用分冶思想，分治模式在每一层递归上有三个步骤：

• 分解：将 n 个元素分成个含 n/2 个元素的子序列
• 解决：用合并排序法对两个子序列递归的排序
• 合并：合并两个已排序的子序列已得到排序结果

动图演示

算法实现

归并排序有两种实现方式，一种是自下而上的迭代，一种是自上而下的递归。我们这里采用递归的方式。
其实明白了思路，就会发现代码很简单，最主要的是明白递归的思想。
分的思想就是一分为二，分为前半部分和后半部分，一次递归分解，直到分为左右均为一个元素。
合并的思想将左右两个有序部分按照顺序合并起来。

const mergeSort = (arr) => {
  if (arr.length < 2) return arr
  const middle = Math.floor(arr.length / 2)
  return merge(mergeSort(arr.slice(0, middle)), mergeSort(arr.slice(middle)))
}
const merge = (left, right) => {
  let result = []
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  if (left.length) result = [...result, ...left]
  if (right.length) result = [...result, ...right]
  return result
}