本文详解归并排序在 javascript 中的正确实现，重点指出原代码中合并循环条件错误、递归调用缺失及逻辑断层等关键问题，并提供可直接运行的完整修复版本。
本文详解归并排序在 javascript 中的正确实现，重点指出原代码中合并循环条件错误、递归调用缺失及逻辑断层等关键问题，并提供可直接运行的完整修复版本。
归并排序（Merge Sort）是一种经典的分治（Divide and Conquer）排序算法，其核心思想是：递归地将数组二分至单元素子数组（此时天然有序），再逐层合并两个已排序的子数组。然而，初学者在实现时常因忽略递归本质或边界条件而陷入“看似结构正确却无法排序”的困境。原代码存在三个关键缺陷，需逐一修正：
? 主要错误分析
mergeTwoSortedArrays 的 while 循环条件错误
原代码使用 while (imergeSort 缺失递归调用
原函数仅对原始数组做一次二分（c 和 d），但未对 c 和 d 本身递归调用 mergeSort，而是直接传入未排序的子数组给 mergeTwoSortedArrays。这导致合并操作始终在“未排序数据”上进行，完全违背归并排序前提——必须确保传入 mergeTwoSortedArrays 的两个参数已是各自有序的数组。命名与职责混淆
solve 方法调用 mergeSort，但 mergeSort 实际未执行完整排序流程；且方法名 mergeSort 与 mergeSortFunction 不一致，增加理解成本。应统一为语义清晰的命名（如 mergeSortFunction → mergeSort），并确保入口方法职责明确。
✅ 修复后的完整实现
以下为修复所有问题、符合标准归并排序逻辑的可运行代码：
const mergeSort = {
solve: function (A) {
return this.mergeSort(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 (i < A.length) C[k++] = A[i++];
while (j < B.length) C[k++] = B[j++];
return C;
},
mergeSort: function (a) {
const n = a.length;
if (n <= 1) return a; // 基础情况：单元素或空数组直接返回
// ✅ 二分：严格按索引切分，避免 Math.floor 引发的歧义（对偶数/奇数均适用）
const mid = Math.floor(n / 2);
const left = a.slice(0, mid); // [0, mid)
const right = a.slice(mid); // [mid, end)
// ✅ 关键修复：递归排序左右子数组，再合并
return this.mergeTwoSortedArrays(
this.mergeSort(left),
this.mergeSort(right)
);
}
};
// ? 使用示例
const inputArray = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = mergeSort.solve(inputArray);
console.log(sortedArray);
// 输出: [3, 9, 10, 27, 38, 43, 82]⚠️ 注意事项与最佳实践
- 避免原地修改风险：本实现全程使用 slice() 创建新数组，确保纯函数特性（无副作用）。若需原地排序，须改用索引参数传递（如 mergeSort(arr, left, right)），但复杂度显著上升，初学阶段不建议。
- 稳定性保障：mergeTwoSortedArrays 中使用
- 时间复杂度：严格保持 $O(n \log n)$，不受输入数据分布影响；空间复杂度为 $O(n)$，主要消耗在临时合并数组 C 及递归调用栈。
- 调试技巧：可在 mergeSort 中添加 console.log('Split:', left, 'and', right)，或在 mergeTwoSortedArrays 返回前打印 C，直观验证分治与合并过程是否符合预期。
掌握归并排序的关键，在于深刻理解“分治”的闭环逻辑：分（Divide）→ 治（Conquer via recursion）→ 合（Combine）。任何一环断裂（如遗漏递归），都将导致算法退化为无效的数组拼接。通过本次修复，你不仅解决了具体 Bug，更夯实了对分治范式本质的认知基础。
立即学习“Java免费学习笔记（深入）”；
