活动地址：CSDN21天学习挑战赛

归并排序思想

先将数据集分解成一组只有一个元素的数组，然后创建一组子数组将他们慢慢合并起来，每次合并都保存一部分排好序的数据，直到最后剩下的这个数组所有的数据都已完美排序。

子数组合并的规则

分组1和分组2的第一个元素进行比较，如果分组1的第一个元素比分组2的第一个元素大，把分组2的第一个元素放进合并后的数组的第一个位置，分组2指针向后移一位。此时，分组1的第一个与分组2的第二个比较，如果分组1的第一个元素比分组2的第二个元素小，分组1的第一个元素放进合并后的数组的第二个位置，分组1的指针向后移一位。此时，分组1的第二个元素和分组2的第二个元素比较，如果分组1的第二个元素比分组2的第二个元素小，把分组1的第二个元素放进合并后的数组的第三个位置上，分组1的指针向后移一位。分组1的第三个元素与分组2的第二个元素比较，如果分组1的第三个元素比分组2的第二个元素小，把分组1的第三个元素放在合并后的数组的第四个位置上，把分组2剩余的数据依次放在合并后的数组的后面的位置上。

归并排序代码

递归方式

function mergeSort(arr) {
  if (arr.length < 2) {
    return;
  }
  subGroupSort(arr, 0, arr.length - 1);
}
// 对子分组进行排序
function subGroupSort(arr, l, r) {
  if (l === r) {
    return;
  }
  let mid = l + ((r - l >> 1));
  // 对左子组排序
  subGroupSort(arr, l, mid);
  // 对右子组排序
  subGroupSort(arr, mid + 1, r);
  // 把排好序的两个子组合并
  merge(arr, l, mid, r);
}
// 合并两个分组
function merge(arr, l, m, r) {
  let help = [];
  let i = 0;
  let p1 = l;
  let p2 = m + 1;
  while (p1 <= m && p2 <= r) {
    help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  }
  // 要么p1越界，要么p2越界，不可能同时越界
  while (p1 <= m) {
    help[i++] = arr[p1++];
  }
  while (p2 <= m) {
    help[i++] = arr[p2++];
  }
  for (i = 0; i < help.length; i++) {
    arr[l + i] = help[i];
  }
}

非递归方式

function mergeSort(nums) {
  if (nums.length === 0) {
    return [];
  }
  let left, right;
  let step = 1;

  while (step < nums.length) {
    left = 0;
    right = step;
    while (right + step <= nums.length) {
      mergeArray(nums, left, left + step, right, right + step);
      left = right + step;
      right = left + step;
    }
    if (right < nums.length) {
      mergeArray(nums, left, left + step, right, nums.length);
    }
    step *= 2;
  }

  function mergeArray(arr, startLeft, stopLeft, startRight, stopRight) {
    let leftArray = new Array(stopLeft - startLeft + 1);
    let rightArray = new Array(stopRight - startRight + 1);
    let k = startRight;
    for (let i = 0; i < rightArray.length - 1; i++) {
      rightArray[i] = arr[k];
      k++;
    }
    k = startLeft;
    for (let i = 0; i < leftArray.length - 1; i++) {
      leftArray[i] = arr[k];
      k++;
    }
    leftArray[leftArray.length - 1] = Infinity;
    rightArray[rightArray.length - 1] = Infinity;
    let m = 0;
    let n = 0;
    for (let i = startLeft; i < startRight; i++) {
      if (leftArray[m] < rightArray[n]) {
        arr[i] = leftArray[m];
        m++;
      } else {
        arr[i] = rightArray[n];
        n++;
      }
    }
  }
}

复杂度分析

时间复杂度

对千长度为 的排序表，二路归并需要进行「log 趟，每趟归并时间为 O(n) 故其时间复杂度无论是在最好还是在最 情况下均是 0(n og 显然平均时间复杂度也是O(nlogn)

空间复杂度

在二路归并排序过程中，每次二 归并都需要使用一个辅助数组来暂存两个有序子表归并 结果 ，而每次 路归并后都会释放其空间，但最后 趟需要所有元素参与归并，所以总的辅助空间复杂度为 O(n)