js实现归并

归并排序原理

归并排序是一种分治算法，通过递归将数组拆分为最小单元（单个元素），再逐步合并有序子数组。核心思想是“分而治之”，时间复杂度为O(n log n)，空间复杂度为O(n)。

递归实现

递归法通过不断二分数组直至长度为1，再合并有序子数组：

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

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

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

  return result.concat(left.slice(i)).concat(right.slice(j));
}

迭代实现

非递归版本使用循环模拟分治过程，避免调用栈过深：

function mergeSort(arr) {
  let step = 1;
  const n = arr.length;

  while (step < n) {
    let l = 0;
    while (l < n) {
      const m = Math.min(l + step, n);
      const r = Math.min(l + 2 * step, n);
      merge(arr, l, m, r);
      l += 2 * step;
    }
    step *= 2;
  }
  return arr;
}

function merge(arr, start, mid, end) {
  const temp = [...arr];
  let i = start, j = mid, k = start;

  while (i < mid && j < end) {
    arr[k++] = temp[i] <= temp[j] ? temp[i++] : temp[j++];
  }

  while (i < mid) arr[k++] = temp[i++];
}

性能优化点

• 小数组切换插入排序：当子数组长度较小时（如<15），插入排序更高效
• 避免重复分配内存：预分配临时数组复用
• 边界检查优化：提前终止已有序数组的合并

复杂度分析

• 时间：始终为O(n log n)，不受输入数据影响
• 空间：需要额外O(n)存储空间
• 稳定性：是稳定排序算法（相等元素不改变相对位置）

使用示例

const arr = [3, 44, 38, 5, 47, 15];
console.log(mergeSort(arr)); // [3, 5, 15, 38, 44, 47]