递归归并排序生成器函数无法按预期分步执行的问题求助

你遇到的核心问题是递归调用的子生成器没有被迭代——原来的代码里，你只是把mergeSort(leftArray)作为普通函数传给了merge，但并没有去遍历这些子生成器的yield步骤，所以只有最外层的一次yield会被执行，内部的递归分割步骤根本不会触发输出。另外，直接在yield后面写console.log也不是最佳实践，应该把要观察的数据作为yield的返回值，这样能更灵活地控制输出。

下面是修正后的完整实现，能让你通过next()一步步查看所有分割（以及可选的合并）步骤：

function* mergeSort(arr) {
  // 递归终止条件：数组长度为1时直接返回
  if (arr.length === 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArray = arr.slice(0, mid);
  const rightArray = arr.slice(mid);

  // 首先yield当前这一步的分割结果，供外部查看
  yield { currentSplit: { left: leftArray, right: rightArray } };

  // 使用yield*委托迭代左子生成器，把左分支的所有yield步骤传递到外层
  const leftSorted = yield* mergeSort(leftArray);
  // 同样处理右子生成器
  const rightSorted = yield* mergeSort(rightArray);

  // 可选：如果你也想观察合并前的有序子数组，可以添加这一步yield
  yield { readyToMerge: { left: leftSorted, right: rightSorted } };

  // 执行合并并返回最终结果
  return merge(leftSorted, rightSorted);
}

// 优化merge函数：用索引遍历替代shift，避免修改原数组且提升性能
function merge(leftArray, rightArray) {
  const sortedArray = [];
  let leftIdx = 0, rightIdx = 0;

  while (leftIdx < leftArray.length && rightIdx < rightArray.length) {
    if (leftArray[leftIdx] < rightArray[rightIdx]) {
      sortedArray.push(leftArray[leftIdx]);
      leftIdx++;
    } else {
      sortedArray.push(rightArray[rightIdx]);
      rightIdx++;
    }
  }

  // 拼接剩余未处理的元素
  return sortedArray.concat(leftArray.slice(leftIdx)).concat(rightArray.slice(rightIdx));
}

如何使用分步查看： #

const list = [32, 12, 23, 52, 5, 16, 74, 21, 33, 55, 85];
const sortGenerator = mergeSort(list);

// 每次调用next()获取下一步的操作
console.log(sortGenerator.next().value); 
// 输出：{ currentSplit: { left: [32,12,23,52,5], right: [16,74,21,33,55,85] } }

console.log(sortGenerator.next().value); 
// 输出：{ currentSplit: { left: [32,12], right: [23,52,5] } }

console.log(sortGenerator.next().value); 
// 输出：{ currentSplit: { left: [32], right: [12] } }

// 继续调用next()就能依次查看所有分割步骤，之后还能看到合并前的有序子数组

关键知识点解释： #

• yield*的作用：它可以把当前生成器的迭代权委托给另一个生成器，子生成器里的所有yield都会被传递到外层生成器，这样递归的每一层分割步骤都能被分步获取。
• 避免重复递归：我们用leftSorted = yield* mergeSort(leftArray)的方式，既完成了子生成器的迭代，又获取了排序后的左数组，避免了重复调用递归函数。
• 不修改原数组：优化后的merge函数用索引遍历替代shift，避免了对原数组的修改，同时shift是O(n)复杂度，索引遍历是O(1)，性能更优。

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