归并排序

归并排序是一种分治算法。其思想是将大数组切分成多个较小的数组，直到每个小数组只有一个元素，接着将小数组归并成较大数组，最终结果是一个已经排好序的数组。归并排序是第一个可以实际使用的排序算法。冒泡排序、选择排序、插入排序算法性能不好，但归并排序性能不错。

不同的浏览器厂商实现 Array.prototype.sort 方式不同，其中 Mozilla FireFox 使用归并排序实现，而 Chrome v8 使用一种快速排序的变体实现。

算法步骤

1. 由于算法是递归的，需要一个终止条件，在这里是判断数组只有一个元素即终止。
2. 如果数组长度比 1 大，那么以索引中间位为界，将其分成两个小数组。这样逐层递归下去，直到被拆分为只有一个元素的数组。这步是分治。
3. 合并两个有序数组，直到回到原始数组并已排序完成。

代码实现

function mergeSort(nums) {
  if (nums.length > 1) {
    const length = nums.length;
    const middle = Math.floor(length / 2);
    const left = mergeSort(nums.slice(0, middle));
    const right = mergeSort(nums.slice(middle, length));
    nums = merge(left, right);
  }

  return nums;
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++]);
  }

  return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

复杂度分析

时间复杂度：归并排序的时间复杂度是 O(nlog(n))。