排序算法5-归并排序

归并排序

• 平均时间复杂度:O(nlogn)
• 最好情况:O(nlogn)
• 最坏情况:O(nlogn)
• 空间复杂度:O(n)
• 排序方式:Out-place
• 稳定性:稳定

算法步骤:
1.需要申请额外空间
2.将序列分为两组，将这两组排序后，再归并成一组。(如何排序见3，如何归并见4)
3.将待排序序列重复操作2，直到只剩下一个元素则已排列。
4.两个有序序列起始位置各有一指针，谁小谁先入列并将指针后移，直到某一指针到达序列尾。然后将另一序列剩余元素全部入列。

function mergeSort(arr) {
  let len = arr.length;
  if (len < 2) return arr;
  let middle = len >> 1;
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(arr1, arr2) {
  let len1 = arr1.length,
    len2 = arr2.length;
  let i1 = 0,
    i2 = 0;
  let result = [];
  while (i1 < len1 && i2 < len2) {
    if (arr1[i1] <= arr2[i2]) result.push(arr1[i1++]);
    else result.push(arr2[i2++]);
  }
  while (i1 < len1) result.push(arr1[i1++]);
  while (i2 < len2) result.push(arr2[i2++]);
  return result;
}

改进
优化1 当序列规模小于某个值时使用插入排序
优化2 当待归并的两个序列前一个序列的尾小于后一个序列的头时说明已经是有序的不需要归并

另外由于使用的是js语言，可能递归过深导致报错，这里可以改成自下而上的方式。代码如下

function mergeSort(arr) {
  let len = arr.length;
  let s = 1;
  while (s < len) {
    for (let i = 0; i < len; i += 2 * s) {
      merge(arr, i, i + s - 1, i + s, i + s * 2 - 1);
    }
    s *= 2;
  }
}

function merge(arr, s1, e1, s2, e2) {
  let len = arr.length;
  if (e1 >= len) return;
  if (e2 >= len) e2 = len - 1;
  let arr1 = arr.slice(s1, e1 + 1);
  let arr2 = arr.slice(s2, e2 + 1);
  let index = s1;
  e1 -= s1;
  s1 = 0;
  e2 -= s2;
  s2 = 0;

  while (s1 <= e1 && s2 <= e2) {
    if (arr1[s1] <= arr2[s2]) arr[index++] = arr1[s1++];
    else arr[index++] = arr2[s2++];
  }
  while (s1 <= e1) arr[index++] = arr1[s1++];
  while (s2 <= e2) arr[index++] = arr2[s2++];
}