在 freeCodeCamp 课程中实现归并排序：divide-and-conquer 策略的完整实践

merge sort（归并排序）是与 quick sort 并列的两种经典中间难度排序算法之一，采用分治（divide-and-conquer）递归策略，稳定达到 O(nlog(n)) 的时间复杂度。freeCodeCamp 的 coding-interview-prep 课程在 algorithms 区块中设置了名为 "Implement Merge Sort" 的编程挑战，要求学习者在不使用内置 .sort() 方法的前提下，手写一个 mergeSort 函数完成整数数组的升序排序。读完本文，你将掌握归并排序"先拆分、后合并"的完整执行模型，理解 merge 与 mergeSort 两个函数如何分工协作，并能对照课程的 4 项断言测试（排序正确性、元素完整性、禁用内置排序）写出可复现的参考实现。

挑战在课程体系中的位置

从课程结构看，该挑战文件 587d825c367417b2b2512c8f.md 归属于 coding-interview-prep 超块下的 algorithms 区块。根据 超块配置，该超块共包含 algorithms、data-structures、take-home-projects 三个区块；而 区块配置中列出的 10 道挑战里，排序算法部分依次为：

顺序	挑战	文件
1	Implement Bubble Sort	8d5123c8c441eddfaeb5bdef.md
2	Implement Selection Sort	587d8259367417b2b2512c85.md
3	Implement Insertion Sort	587d8259367417b2b2512c86.md
4	Implement Quick Sort	587d825a367417b2b2512c89.md
5	Implement Merge Sort（本挑战）	587d825c367417b2b2512c8f.md
6	Implement Binary Search	61abc7ebf3029b56226de5b6.md

也就是说，学习者先完成了三个 O(n²) 级别的初阶排序和一个 O(nlog(n)) 的快排，才会遇到本挑战。这与课程文档的定位一致——merge sort 被描述为"另一个常见的中间难度排序算法"（another common intermediate sorting algorithm），且是课程明确覆盖的最后一个排序算法；文档同时预告，后续在树形数据结构部分还会介绍依赖二叉堆的 heap sort。

算法核心思想：为什么两个有序数组容易合并

课程文档对归并排序原理的表述是：合并两个已经各自有序的数组相对容易；但输入只是一个未排序的数组，如何从它出发得到两个有序数组？答案就是递归拆分——不断把原数组对半切分，直到到达"单元素数组"这一基准情形（base case）。单元素数组天然有序，于是可以开始自底向上合并，合并过程逐层展开（unwind）拆分阶段产生的递归调用，最终产出包含全部元素的有序数组。

由此可以概括出文档给出的两步模型：

1） 递归地将输入数组一分为二，直到产生只含一个元素的子数组。

2） 将每个有序子数组两两合并，产出最终排序数组。

从源码结构看，这种"先全部拆到叶子、再逐层合并"的写法正是分治策略中"自顶向下递归 + 自底向上归并"的标准形态：递归树的深度为 log(n)，每一层所有合并操作的总工作量为 O(n)，合计得到 O(nlog(n))。文档也基于此给出该算法的时间复杂度结论：O(nlog(n))，并指出归并排序之所以流行，正是因为它性能良好且相对容易实现。

任务要求：两个函数的职责划分

文档给出的指令（Instructions）原文要求：编写一个 mergeSort 函数，接收整数数组，返回按从最小到最大排序后的数组。文档特别推荐了一种实现方式：

• merge 函数：负责合并两个已排序的数组；
• mergeSort 函数：负责递归拆分，产生单元素数组并喂给 merge。

编辑器的初始种子代码（seed）是：

function mergeSort(array) {
  // Only change code below this line
  return array;
  // Only change code above this line
}

学习者只需替换中间的两行注释之间的逻辑。值得注意的是，课程允许在 mergeSort 函数体内声明嵌套的 merge 辅助函数——参考解法正是这种组织方式。

参考解法逐行解析

挑战文档内置的 --solutions-- 段提供了官方参考解法，这里结合其内嵌注释做逐段解析：

function mergeSort(array) {
  if (array.length === 1) {
    return array;
  } else {
    const splitIndex = Math.floor(array.length / 2);
    return merge(
      mergeSort(array.slice(0, splitIndex)),
      mergeSort(array.slice(splitIndex))
    );
  }

  // Merge two sorted arrays
  function merge(array1, array2) {
    let merged = [];
    while (array1.length && array2.length) {
      if (array1[0] < array2[0]) {
        merged.push(array1.shift());
      } else if (array1[0] > array2[0]) {
        merged.push(array2.shift());
      } else {
        merged.push(array1.shift(), array2.shift());
      }
    }

    // After looping ends, one array is empty, and other array contains only
    // values greater than all values in `merged`
    return [...merged, ...array1, ...array2];
  }
}

mergeSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]);

递归拆分部分

• 基准情形：array.length === 1 时直接返回，对应上文"单元素数组天然有序"的论证。
• 拆分点 Math.floor(array.length / 2)：向下取整保证左半部分可能比右半部分短一个元素（如长度为 5 时，左 2 右 3），但两侧都非空，递归必然终止。
• array.slice(0, splitIndex) 与 array.slice(splitIndex) 生成两个副本，这是非破坏性操作——课程测试恰好依赖这一点（见下文 assert.sameMembers 验证元素未被修改）。

合并部分

merge(array1, array2) 的循环不变式是：两个输入数组始终各自有序，且头部元素分别是其中的最小值。

• 每次比较 array1[0] 与 array2[0]，把较小者 shift() 出来推入 merged。
• 相等分支 merged.push(array1.shift(), array2.shift()) 一次性弹出两个元素，这是处理重复值（本测试数组中 123、43、2、1 均出现两次）的关键，等价于把相等的两个元素都纳入结果。
• 循环结束后，两个数组中必有一个已空，另一个的剩余元素大于 merged 中所有值（因为此前每一轮弹出的都是当前双头最小值）。因此直接展开拼接 [...merged, ...array1, ...array2] 即可，无需再排序。

从实现细节看，shift() 是 O(n) 操作，因此这段参考解法中 merge 的理论代价高于用双指针索引遍历的 O(n) 版本；但课程目标是验证算法结构理解而非极致性能，这一写法以可读性优先。

四项断言测试与约束条件

课程通过 4 条断言来验证实现，逐条拆解可得到完整的"验收标准"：

1. mergeSort 必须是函数

assert.isFunction(mergeSort);

2. 返回值必须是从最小到最大的有序数组

文档提供了一个通用的 isSorted 校验器：

function isSorted(a){
  for(let i = 0; i < a.length - 1; i++)
    if(a[i] > a[i + 1])
      return false;
  return true;
}
assert.isTrue(
  isSorted(
    mergeSort([
      1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92
    ])
  )
);

3. 元素构成不得改变（只能重排，不能增删）

assert.sameMembers(
  mergeSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]),
  [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
);

assert.sameMembers 以多重集（multiset）语义比较两个数组：元素及出现次数必须完全一致，仅顺序可以不同。这直接呼应了文档指令中"except for order"（除顺序外不变）的约束——注意测试数据中刻意包含重复值，因此用 Set 之类的去重手段去"凑答案"会在这里失败。

4. 禁止使用内置 .sort()

function isBuiltInSortUsed(){
  let sortUsed = false;
  const temp = Array.prototype.sort;
  Array.prototype.sort = () => sortUsed = true;
  try {
    mergeSort([0, 1]);
  } finally {
    Array.prototype.sort = temp;
  }
  return sortUsed;
}
assert.isFalse(isBuiltInSortUsed());

这条断言通过猴子补丁（monkey patch）手段将 Array.prototype.sort 替换为置位标记函数，调用被测代码后在 finally 中恢复原型。只要 mergeSort 内部任何位置（包括借助其他库间接调用）触碰了 .sort，断言即失败。这保证了学习者真正实现了排序逻辑，而不是"调一下内置方法"。

此外，测试使用的 17 元素数组 [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92] 与前一挑战 Implement Quick Sort 中的断言数据完全相同，从源码结构看，课程的排序算法挑战共享同一组基准测试数据，便于横向对比不同算法实现的正确性。

递归展开示例

以小型数组 [3, 1, 4, 2] 为例，可以直观看到文档所述"拆到单元素再逐层合并"的过程：

            [3, 1, 4, 2]
           /            \
       [3, 1]          [4, 2]
       /    \          /    \
    [3]    [1]      [4]    [2]        <- 基准情形：单元素，天然有序
       \    /          \    /
       [1, 3]          [2, 4]        <- 合并两个有序单元素
           \            /
           [1, 2, 3, 4]              <- 合并两个有序子数组

每一层合并都只依赖两个输入各自有序这一前提，与上文 merge 函数的循环不变式一一对应。

常见实现细节与易错点

基于文档解法与断言设计，可以归纳出几个容易踩坑的地方：

1. 拆分边界：Math.floor(array.length / 2) 之后必须保证左右两部分都不为空，否则递归不会终止。对于长度为 2 的数组，切分结果为 [a] 和 [b]，正好落入基准情形。
2. 相等元素的处理：参考解法在 array1[0] === array2[0] 时同时弹出两个元素。如果只弹出其一，另一相等元素会留在数组中等待下一轮比较，结果依然正确（这是归并排序稳定性的体现之一）；但若写成 else 分支只处理了 > 而漏掉 =，逻辑上依赖数组自然结束，容易引发困惑。
3. 不要原地修改输入：断言 3 的 sameMembers 虽只比较多重集成员，但 slice 生成副本的写法天然满足"不改变入参"的整洁语义。
4. shift() 的性能代价：如上所述，频繁 shift 会使合并过程退化为 O(n²) 级别。若追求效率，可改用两个索引指针遍历输入数组，把 O(n) 的合并恢复到线性复杂度——这是课程未要求但值得了解的优化方向。

小结

本挑战以"拆分到单元素 + 两两有序合并"两步模型，把归并排序的递归结构讲得非常收敛：mergeSort 负责自顶向下的分裂并触发递归，merge 负责自底向上的线性归并，两者共同实现了文档所述的 O(nlog(n)) 排序。对照课程的四项断言——函数存在、升序输出、元素多重集不变、禁用内置 .sort——可以清楚地界定"合格的归并排序实现"的边界。完成该挑战后，学习者即已走完 algorithms 区块中从冒泡、选择、插入、快排到归并的全部排序算法序列，下一步则是 Implement Binary Search：在有序数组上做 O(log n) 查找，与本文的排序产出正好衔接。