请问这份迭代实现的归并排序是否正确？其时间/空间复杂度如何？

嘿，这个实现确实挺巧妙的——初看简洁，但细品下来确实容易让人摸不着头脑，我来帮你拆解下它的逻辑、复杂度，以及可能存在的问题～

先理清楚实现逻辑 #

你的代码是自底向上的迭代式归并排序，和常见的递归拆分（自顶向下）思路不同，它是从单个元素的子数组开始，逐步合并相邻的有序子数组：

• 第一步：把原数组的每个元素都包装成单元素数组，这相当于归并排序的“拆分到最小单元”阶段，只不过是直接生成，而非递归拆分。
• 第二步：进入循环，只要数组长度大于1，就遍历当前数组，每两个相邻的子数组合并成一个有序数组，并用splice把这两个子数组替换成合并后的结果，直到最终只剩一个完整的有序数组。

时间复杂度：比常规归并排序差很多 #

你的测试用例能通过，但时间复杂度确实有明显的退化问题，核心原因是**splice操作的开销**：

• 常规的自底向上归并排序时间复杂度是O(n log n)，因为每一轮合并所有元素的总时间是O(n)，总共需要O(log n)轮（每次合并后子数组数量减半，直到只剩1个）。
• 但你的实现里，arr.splice(i, 2, mergeTwoSortedArrays(...))会在原数组上直接修改，而splice在数组中间删除/插入元素时，需要移动后面所有的元素，每次splice的时间复杂度是O(k)（k是当前数组中需要移位的元素数量）。
• 每一轮合并时，你需要执行ceil(len/2)次splice，每次移位的元素数量累加起来是O(n²)级别（比如第一轮n个元素，移位总次数是(n-2)+(n-4)+...+2 = O(n²)）。再乘以O(log n)轮，总时间复杂度会退化到**O(n² log n)**，这比常规归并排序的效率低很多，数据量越大，差距越明显。

空间复杂度：和常规归并持平 #

空间复杂度方面，这个实现是**O(n)**：

• 所有合并后的子数组加起来的元素总数始终是n（从n个单元素数组，到最终1个完整数组，总元素数不变）。
• 虽然每次合并会创建新的数组，但临时的合并结果数组最终都会被替换，不会额外占用更多空间，这一点和常规自底向上归并排序的空间复杂度一致。

优化建议：避免使用splice，改用临时数组存储合并结果 #

要把时间复杂度拉回O(n log n)，可以不用在原数组上splice，而是每一轮用一个临时数组来存储合并后的所有子数组，比如：

function mergeSort(arr) {
  let subarrays = arr.map(item => [item]);
  while (subarrays.length > 1) {
    const merged = [];
    for (let i = 0; i < subarrays.length; i += 2) {
      const first = subarrays[i];
      const second = subarrays[i + 1] || [];
      merged.push(mergeTwoSortedArrays(first, second));
    }
    subarrays = merged;
  }
  return subarrays[0];
}

这个版本用临时数组merged存储每一轮的合并结果，避免了splice带来的元素移位开销，时间复杂度回到O(n log n)，逻辑也更清晰。

内容的提问来源于stack exchange，提问作者LFJ