JavaScript不使用内置方法实现归并排序的bug排查求助

问题原因 #

代码的核心问题出在合并两个有序子数组的剩余元素处理步骤：
原有逻辑仅对剩余的单个元素做了赋值，当左/右临时数组中剩余未处理元素数量大于1时，后续元素会全部遗漏，导致原数组对应位置残留旧值，最终排序结果不符合预期。

修复方法 #

将合并函数末尾的单行剩余元素处理代码，替换为两个循环，分别将左右临时数组中未遍历完的所有元素依次写入原数组：

// 替换原有错误的剩余元素处理逻辑
// i < lArray.length ? arr[k] = lArray[i] : arr[k] = rArray[j];

// 修复后逻辑：处理左数组剩余元素
while (i < lArray.length) {
  arr[k] = lArray[i];
  i++;
  k++;
}
// 处理右数组剩余元素
while (j < rArray.length) {
  arr[k] = rArray[j];
  j++;
  k++;
}

修复后完整可运行代码 #

// Merge Sort implementation

// 合并两个有序子数组
function merge(arr, start, mid, end) {
  // 创建并填充临时数组
  let lArray = [];
  let rArray = [];

  for (let i = 0; i <= mid - start; i++) {
    lArray[i] = arr[start + i];
  }

  for (let j = 0; j <= end - mid - 1; j++) {
    rArray[j] = arr[mid + 1 + j];
  }

  // 合并两个临时数组到原数组
  let i = 0;
  let j = 0;
  let k = start;

  while (i < lArray.length && j < rArray.length) {
    if (lArray[i] < rArray[j]) {
      arr[k] = lArray[i];
      i++;
    } else {
      arr[k] = rArray[j];
      j++;
    }
    k++;
  }

  // 处理左数组剩余元素
  while (i < lArray.length) {
    arr[k] = lArray[i];
    i++;
    k++;
  }
  // 处理右数组剩余元素
  while (j < rArray.length) {
    arr[k] = rArray[j];
    j++;
    k++;
  }
}

// 递归归并排序 
function recursiveMergeSort(arr, start, end) {
  if (start < end) {
    let mid = Math.floor((end + start) / 2);
    recursiveMergeSort(arr, start, mid);
    recursiveMergeSort(arr, mid + 1, end);
    merge(arr, start, mid, end);
  }
}

function mergeSort(arr) {
  let start = 0;
  let end = arr.length - 1;
  recursiveMergeSort(arr, start, end);
  return arr;
}

console.log(mergeSort([5, 8, 3, 7, 5])); // 输出 [3, 5, 5, 7, 8] 符合预期

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