归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4. 重复步骤 3 直到某一指针达到序列尾；

5. 将另一序列剩下的所有元素直接复制到合并序列尾。

动图演示

代码实现

// 从小到大
// 递归算法复杂度为O(logn)加上merge的复杂度=>O(nlogn)
function mergeSort(arr) {
  const len = arr.length
  if (len < 2) {
    return arr
  }
  const index = Math.floor(len / 2)
  const left = arr.slice(0, index)
  const right = arr.slice(index)
  return merge(mergeSort(left), mergeSort(right))
}

// left和right传入的时候已经是有序的数组了
// 复杂度为O(n)
function merge(left, right) {
  const result = []

  while (left.length && right.length) {
    if (left[0] > right[0]) {
      result.push(right.shift())
    } else {
      result.push(left.shift())
    }
  }

  if (left.length) {
    result.push(...left)
  }
  if (right.length) {
    result.push(...right)
  }

  return result
}

let arr = [6, 3, 5, 2, 4, 1]

arr = mergeSort(arr)

console.log(arr)