如何不使用sort方法及冒泡、快排等排序算法合并两个有序数组

我在一次面试中被问到了这个问题，我给出的答案和下方实现类似，因为最终的循环存在问题，该答案是错误的。

const newSortArrays = (arr1, arr2) => {
     let output = [];
     while (arr1.length && arr2.length) {
        if (arr1[0] < arr2[0]) 
         output.push(arr1[0] < arr2[0] ? arr1.shift() : arr2.shift())
     }
     return [...output, ...arr1, ...arr2]
 }

核心问题点 #

• 缺else分支导致死循环：你只在arr1[0] < arr2[0]的条件下执行了push逻辑，一旦出现arr1[0] >= arr2[0]的情况，if条件不满足，循环体内没有任何代码执行，两个数组的长度永远不会变化，while循环的判断条件arr1.length && arr2.length永远为真，程序会直接卡死。
• 逻辑冗余：你已经在if条件中做了一次arr1[0] < arr2[0]的判断，push里的三元判断是完全多余的重复操作。

修正后的代码 #

如果可以接受修改传入的原始数组，直接删掉多余的if外层判断即可：

const newSortArrays = (arr1, arr2) => {
  const output = [];
  while (arr1.length && arr2.length) {
    // 直接比较队首元素，把更小的压入结果数组
    output.push(arr1[0] < arr2[0] ? arr1.shift() : arr2.shift());
  }
  // 拼接剩下的有序元素
  return [...output, ...arr1, ...arr2];
}

如果更偏好if-else写法，也可以改写为：

const newSortArrays = (arr1, arr2) => {
  const output = [];
  while (arr1.length && arr2.length) {
    if (arr1[0] < arr2[0]) {
      output.push(arr1.shift());
    } else {
      output.push(arr2.shift());
    }
  }
  return [...output, ...arr1, ...arr2];
}

补充说明 #

如果需求要求不修改传入的原始数组，可以用双指针的方式实现，避免shift操作对原数组的影响：

const newSortArrays = (arr1, arr2) => {
  const output = [];
  let i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      output.push(arr1[i++]);
    } else {
      output.push(arr2[j++]);
    }
  }
  // 拼接剩余元素
  return [...output, ...arr1.slice(i), ...arr2.slice(j)];
}

内容的提问来源于stack exchange，提问作者newby-prom