每日一算法：归并排序

归并排序（Merge sort）是最流行的排序算法之一。该算法是采用分治法的一个非常文章
典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现有两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

归并只做两件事：

• 把它的输入分成几个小节，直到每个小节只剩下一个元素。
• 将其所有子部分合并（并排序）为一个现在已排序的大部分。

JavaScript 实现

使用归并排序算法对数字数组进行排序。

• 使用递归。
• 如果 length 数组的小于 2，则返回数组。
• 使用 Math.floor() 计算数组的中间点。
• 使用 Array.prototype.slice() 将数组切成两部分，然后递归调用 mergeSort() 所创建的子数组。
• 最后，使用 Array.from() 和 Array.prototype.shift() 将两个排序的子数组组合为一个。

const mergeSort = arr => {
  if (arr.length < 2) return arr
  const mid = Math.floor(arr.length / 2)
  const l = mergeSort(arr.slice(0, mid))
  const r = mergeSort(arr.slice(mid, arr.length))
  return Array.from({ length: l.length + r.length }, () => {
    if (!l.length) return r.shift()
    else if (!r.length) return l.shift()
    else return l[0] > r[0] ? r.shift() : l.shift()
  })
}

mergeSort([5, 1, 4, 2, 3]) // [1, 2, 3, 4, 5]

此示例来自 30 seconds of code 的 mergeSort