本文详解归并排序在 javascript 中的典型实现错误（如合并循环条件冗余、递归调用缺失），提供可运行的修正代码，并说明分治逻辑、边界处理及性能注意事项。
本文详解归并排序在 javascript 中的典型实现错误（如合并循环条件冗余、递归调用缺失），提供可运行的修正代码，并说明分治逻辑、边界处理及性能注意事项。
归并排序是一种经典的分治（Divide and Conquer）排序算法，其核心思想是：将数组递归地二分直至子数组长度为 1（天然有序），再逐层合并两个已排序的子数组。然而，初学者在实现时极易忽略关键细节，导致结果错误或无限递归。原代码存在两个根本性缺陷：
mergeTwoSortedArrays 中的 while 循环条件错误：
原写法 while (i < A.length && j < B.length && A[i] || B[j]) 混淆了逻辑判断——A[i] || B[j] 会因 0、null 或 undefined 等 falsy 值提前终止循环（例如当 A = [0, 2]、B = [1, 3] 时，A[0] === 0 导致条件为 false，循环直接退出）。正确条件应仅为 i < A.length && j < B.length，仅控制索引不越界。mergeSort 函数未递归调用自身：
原代码直接对未排序的左右子数组 c 和 d 调用 mergeTwoSortedArrays，而未先递归排序它们。这导致合并操作始终作用于原始乱序片段，完全违背归并排序的“先分后治”原则。
以下是修复后的完整、可直接运行的实现：
const mergeSort = {
solve: function (A) {
return this.mergeSortFunction(A);
},
mergeTwoSortedArrays: function (A, B) {
let i = 0, j = 0, k = 0;
const C = [];
// ✅ 正确条件：仅检查索引边界
while (i < A.length && j < B.length) {
if (A[i] <= B[j]) { // 使用 <= 保证稳定性（相等时优先取左）
C[k++] = A[i++];
} else {
C[k++] = B[j++];
}
}
// ✅ 补充剩余元素（无需再判空，因 while 已确保仅一方有剩余）
while (i < A.length) C[k++] = A[i++];
while (j < B.length) C[k++] = B[j++];
return C;
},
mergeSortFunction: function (a) {
const n = a.length;
if (n <= 1) return a; // 基础情况：长度 ≤1 直接返回
// ✅ 正确分割：左半部分 c，右半部分 d
const mid = Math.floor(n / 2);
const c = a.slice(0, mid); // 推荐使用 slice() 替代 Array.from + 映射，更简洁安全
const d = a.slice(mid);
// ✅ 关键修复：递归排序左右子数组后再合并
return this.mergeTwoSortedArrays(
this.mergeSortFunction(c),
this.mergeSortFunction(d)
);
}
};
// ✅ 使用示例
const inputArray = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = mergeSort.solve(inputArray);
console.log(sortedArray); // 输出: [3, 9, 10, 27, 38, 43, 82]关键注意事项与最佳实践：
- 避免原地修改风险：本实现始终返回新数组，不修改输入。若需原地排序，需额外实现 in-place merge（复杂度显著上升，通常不推荐）。
- 稳定性保障：合并时使用 <= 而非 <，确保相等元素的相对顺序不变。
- 分割方式优化：使用 slice(0, mid) 和 slice(mid) 替代手动 Array.from 构造，语义清晰、不易出错，且自动处理空数组边界。
- 时间与空间复杂度：归并排序稳定为 O(n log n) 时间，但需 O(n) 额外空间（用于临时合并数组），这是其与快排的核心权衡点。
通过理解分治逻辑、严格校验循环条件、确保递归完整性，即可写出健壮的归并排序实现。建议结合调试器单步跟踪 mergeSortFunction([3,1,4,1]) 的调用栈，直观掌握“分裂→排序→合并”的全过程。
立即学习“Java免费学习笔记（深入）”；
