排序：归并排序

原理

1. 拆分：将一个数组拆分成两个数组，左数组和右数组。然后声明一个空的新数组。
2. 合并：比较两个数组最前面的元素，把小的移动到新数组里面。注意，移动这个元素之后，该数组里面已经没有该元素了。
3. 重复第二步，直到左右数组其中一个为空。
4. 将左右数组中不为空那一个剩余的元素放到新数组里面。

注意，归并排序是递归调用的。拆分时持续拆分数组，直到左右数组只包含一个元素。然后将这些数组进行合并操作。

例子

归并排序

代码

// 归并排序

/**
 * 归并排序中合并两个数组，并返回结果
 * @param {Array} left
 * @param {Array} right
 * @returns {Array}
 */
const merge = (left, right) => {
  let result = []
  let i = 0
  let j = 0

  while (i < left.length && j < right.length) {

    if (left[i] > right[j]) {
      result.push(right[j++])
    }
    else {
      result.push(left[i++])
    }
  }

  while (i < left.length) {
    result.push(left[i++])
  }

  while (j < right.length) {
    result.push(right[j++])
  }

  return result
}

const mergeSort = (list) => {

  if (list.length < 2) {
    return list
  }

  let middle = Math.floor(list.length / 2)
  let left = list.slice(0, middle)
  let right = list.slice(middle)

  return merge(mergeSort(left), mergeSort(right))
}

代码中，以 i 和 j 对左右数组的遍历来代表移动元素的动作，被移动到新数组的元素实际上还存在于数组中，只是不被遍历了。而上面原理部分说成移动只是为了更好地表述。

延伸

假如写成移动元素的话，即从左右数组中删除原来的元素，推测涉及到删除操作，开销也就更大，代码的性能就会受到影响。简单测试了下，的确是遍历的方式比较快。

// 归并排序（涉及删除数组元素）

/**
 * 归并排序中合并两个数组，并返回结果
 * @param {Array} left
 * @param {Array} right
 * @returns {Array}
 */
const merge2 = (left, right) => {
  let result = []

  while (left.length && right.length) {

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

  while (left.length) {
    result.push(left.shift())
  }

  while (right.length) {
    result.push(right.shift())
  }

  return result
}

const mergeSort2 = (list) => {

  if (list.length < 2) {
    return list
  }

  let middle = Math.floor(list.length / 2)
  let left = list.slice(0, middle)
  let right = list.slice(middle)

  return merge2(mergeSort2(left), mergeSort2(right))
}

/**
 * 生成指定长度与指定最大值的随机数组
 * @param {Number} length 数组长度，默认 50
 * @param {Number} maxValue 数组最大值，默认 100
 * @returns {Array}
 */
const genRandomArray = (length = 50, maxValue = 100) => {
  let arr = []

  for (let i = 0; i < length; i++) {
    arr[i] = Math.ceil(Math.random() * maxValue)
  }

  return arr
}

/**
 * 测试排序一个数组所花费的时间
 * @param {Function} sort 排序算法函数
 * @param {Array} list 待排序数组
 */
const timeTest = (sort, list, sortName) => {
  console.time(sortName)
  sort(list)
  console.timeEnd(sortName)
}

// 测试函数
const test = () => {

  for (let i = 0; i< 10; i++) {
    let list = genRandomArray(100)
    timeTest(mergeSort, list, 'mergeSort')
    timeTest(mergeSort2, list, 'mergeSort2')
    console.log('\n')
  }
}

运行结果如下：

可见，涉及到删除元素的归并排序，虽然写起来代码简洁，可运行起来性能不如遍历形式的。

参考文献

[1] 饥人谷算法教程：选择排序--效率测试
[2] Liang ,Y.Daniel. Java 语言程序设计：进阶篇[M]. 李娜，译. 机械工业出版社，2011：73-76.