题库/手写题/题目详解
专题深化约 3 分钟阅读

手写稳定的归并排序，并分析复杂度与重复项顺序。

先理解原理和示例，再练习完整口述与追问。

回答要点

分治、合并有序序列；相等先取左侧；O(n log n)；辅助空间与递归栈；比较器一致性。

原理拆解

把数组拆为左右两半，分别排序，再用两个游标线性合并。每层总处理 O(n)，拆分深度 O(log n)，所以时间 O(n log n)。合并时相等先取左项，可以保留原有相等元素的相对顺序。该实现使用切片和新数组，不修改输入；峰值辅助空间通常 O(n)，递归栈 O(log n)，累计分配量仍需注意。

示例与推演

js
function mergeSort(input, compare = (a, b) => a - b) {
  if (!Array.isArray(input) || typeof compare !== 'function') throw new TypeError('参数不合法')
  if (input.length < 2) return input.slice()
  const middle = Math.floor(input.length / 2)
  const left = mergeSort(input.slice(0, middle), compare)
  const right = mergeSort(input.slice(middle), compare)
  const result = []
  let i = 0, j = 0
  while (i < left.length && j < right.length) {
    if (compare(left[i], right[j]) <= 0) result.push(left[i++])
    else result.push(right[j++])
  }
  while (i < left.length) result.push(left[i++])
  while (j < right.length) result.push(right[j++])
  return result
}

输入 [{score:1,id:'A'},{score:0,id:'B'},{score:1,id:'C'}]，按 score 排序应得到 B、A、C，相等的 A/C 顺序不变。

易错点

默认比较器面向普通有限数值，不处理 NaN 的业务排序。不要用 shift 消费大数组而忽略移动成本；稳定性也不是所有排序算法天然具有。

参考回答可直接练习口述

归并先递归排左右，再双指针合并，相等先取左侧以保持稳定。时间 O(n log n)，有辅助数组成本，不改输入；比较器和特殊值规则由调用契约决定。