如何基于归并排序实现数组排序Polyfill？解决比较器失效问题

你编写的归并排序Polyfill里比较器失效的核心问题在于merge函数中对比较器的处理逻辑完全错误，同时定义的composeCompareFn函数也未被实际调用。

原代码的关键错误 #

• 在merge函数中，你先尝试赋值newCompareFn，但紧接着又用newCompareFn = (left, right) => left > right完全覆盖了之前的逻辑，导致传入的compareFn根本没被使用
• 未正确处理默认比较器的逻辑，原生Array.sort()默认会将元素转为字符串后按Unicode码点排序
• composeCompareFn函数定义后从未调用，无法将比较器的返回值转换为排序判断的依据

修改后的完整代码 #

const arrA = [2, 3, 4, 1, 2, 3, 1, 5, 6, 8, 5, 9, 3];
const newArr = [...new Set(arrA)];

Array.prototype.myNewSort = function(compareFn) {
  // 处理默认比较器：转为字符串按Unicode码点比较
  const defaultCompare = (a, b) => String(a).localeCompare(String(b));
  // 确定最终使用的比较器
  const finalCompareFn = compareFn || defaultCompare;

  return mergeSort([...this]); // 复制原数组，避免修改原数组

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

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

    return merge(mergeSort(leftArr), mergeSort(rightArr));
  }

  function merge(left, right) {
    let newArr = [];
    let leftIdx = 0;
    let rightIdx = 0;

    // 避免使用shift()，提升性能（shift会修改数组并重新索引）
    while (leftIdx < left.length && rightIdx < right.length) {
      // 根据比较器返回值判断：返回小于0时，a应该排在b前面
      const compareResult = finalCompareFn(left[leftIdx], right[rightIdx]);
      if (compareResult <= 0) {
        newArr.push(left[leftIdx]);
        leftIdx++;
      } else {
        newArr.push(right[rightIdx]);
        rightIdx++;
      }
    }

    // 拼接剩余元素
    return [...newArr, ...left.slice(leftIdx), ...right.slice(rightIdx)];
  }
}

// 测试数字升序
const sortedArr = newArr.myNewSort((a, b) => a - b);
console.log("数字升序排序结果", sortedArr);

// 测试默认排序（字符串Unicode）
const strArr = ['banana', 'apple', 'Cherry'];
console.log("默认字符串排序结果", strArr.myNewSort());

核心修改点 #

1. 正确处理比较器逻辑：确定最终使用的比较器，优先使用用户传入的compareFn，否则使用默认的字符串比较逻辑
2. 修复merge函数的排序判断：根据比较器的返回值（小于等于0时左元素在前，大于0时右元素在前）来决定元素顺序，符合原生sort的规则
3. 优化性能：使用索引遍历替代shift()，避免频繁修改数组结构带来的性能损耗
4. 不修改原数组：在mergeSort开始时复制原数组，保持与原生sort的行为一致
5. 移除无用函数：删除未被调用的composeCompareFn，简化代码

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