本文深入探讨了 javascript 归并排序 实现中常见的错误和优化点，包括 `merge` 函数中结果数组回写逻辑的修正、`right` 参数边界定义的统一（建议采用左闭右开区间）、高效整数除法的应用，以及如何编写更简洁、更符合 javascript 习惯的归并排序代码。通过分析原始问题代码并提供优化方案，旨在帮助开发者构建健壮且高效的归并 排序算法。
归并排序概述
归并排序（Merge sort）是一种基于分治思想的高效稳定 排序 算法 。其基本思想是将待排序序列 递归 地分成两半，直到每个子序列只包含一个元素（自然有序），然后将这些子序列两两合并，每次合并都使子序列有序，直到最终合并成一个完整的有序序列。归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。
常见实现问题与分析
在实现归并排序时，开发者常会遇到一些细节问题，导致代码无法正常工作或效率低下。以下是对一个典型javaScript 归并排序实现中存在问题的详细分析：
原始代码片段
function mergesort(arr, left, right) {if (left < right) {let mid = parseInt((right - left) / 2) + left; mergesort(arr, left, mid); mergesort(arr, mid + 1, right); merge(arr, left, mid, right); } } function merge(arr, left, mid, right) {let i = left, j = mid + 1, k = 0, temp = []; while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k] = arr[i]; i++; k++; } else {temp[k] = arr[j]; j++; k++; } } for (; i <= mid; i++) {temp[k] = arr[i]; k++; } for (; j <= right; j++) {temp[k] = arr[j]; k++; } for (let i = left; i <= right; i++) {// 问题所在 arr[i] = temp[i]; // 错误：这里应该是 temp[i - left]或使用单独的索引 } } let arr = [5, 3, 7, 2, 9, 12, 4]; n = arr.length; mergesort(arr, 0, n); // 问题所在：right 参数通常指最后一个元素的索引，而不是数组长度问题点一：merge 函数中结果数组的回写错误
这是导致输出结果异常（如[undefined, undefined, …, 3, 5]）的核心问题。在 merge 函数的最后，将 temp 数组中的元素复制回原数组 arr 时，使用了相同的索引 i 来同时访问 arr 和 temp。然而，temp 数组是从索引 0 开始填充的，而 arr 的目标区间是从 left 开始的。
错误代码：
立即学习“Java 免费学习笔记（深入）”；
for (let i = left; i <= right; i++) {arr[i] = temp[i]; // 错误！temp[i]可能越界或取到错误的值 }当 i 从 left 开始时，temp[i]可能会访问到 temp 数组中未被赋值的区域（如果 left > 0），导致 undefined。正确做法是使用一个单独的索引来遍历 temp 数组，或者将 temp 数组的索引进行偏移。
修正方案：
for (let idx = 0; idx < k; idx++) {arr[left + idx] = temp[idx]; }这里，idx 从 0 开始遍历 temp 数组，而 arr 的写入位置通过 left + idx 进行偏移，确保将 temp 中的元素正确地放置到 arr 的相应子区间。
问题点二：初始调用 mergesort 时 right 参数的语义不一致
在原始代码中，mergesort(arr, left, right)函数的 right 参数被期望是子数组的最后一个元素的索引。然而，在初始调用 mergesort(arr, 0, n)时，n 是数组的长度，这意味着 right 实际上是数组最后一个元素索引的“后一位”。这种不一致性会导致在处理边界条件时出现问题，例如当 right 为 n 时，arr[right]会尝试访问越界元素。
修正方案： 统一 right 参数的语义。更符合 javascript 等语言习惯的做法是，将 right 定义为子数组的结束索引（不包含该索引），即 左闭右开区间 [left, right)。
问题点三：整数除法的效率问题
计算中间索引 mid 时使用了 parseInt((right – left) / 2) + left。这种方法涉及浮点运算、字符串 转换和整数解析，效率较低。
修正方案： 使用 位运算符>> 1 进行整数除法，这是一种更高效且常用的方法。
问题点四：merge 函数中冗余的元素复制
在 merge 函数中，有两个 for循环 用于复制剩余元素：
for (; i <= mid; i++) {temp[k] = arr[i]; k++; } for (; j <= right; j++) {temp[k] = arr[j]; k++; }当采用“左闭右开”的 right 参数语义时，这两个循环的条件会相应改变。实际上，如果 right 表示不包含的结束索引，并且 temp 数组在合并过程中只包含合并后的元素，那么在主 while 循环结束后，i 或 j 中的一个会到达其边界，另一个则指向剩余元素。这些剩余元素可以直接追加到 temp 中。
优化后的归并排序实现
综合上述分析和修正，以下是采用“左闭右开”区间语义的优化版归并排序实现。这种实现方式在 JavaScript 中更为常见和推荐。
/** * 归并排序主函数 * @param {Array<number>} arr 待排序数组 * @param {number} left 子数组的起始索引 (包含） * @param {number} right 子数组的结束索引 (不包含） */ function mergesort(arr, left, right) {// 当子数组长度大于 1 时才进行排序 if (right - left > 1) {// 计算中间索引，采用位运算提高效率 let mid = left + ((right - left) >> 1); // 递归排序左半部分 [left, mid) mergesort(arr, left, mid); // 递归排序右半部分 [mid, right) mergesort(arr, mid, right); // 合并两个有序子数组 merge(arr, left, mid, right); } } /** * 合并两个有序子数组 * @param {Array<number>} arr 原始数组 * @param {number} left 左子数组的起始索引 (包含） * @param {number} mid 左子数组的结束索引 (不包含），同时也是右子数组的起始索引 (包含） * @param {number} right 右子数组的结束索引 (不包含） */ function merge(arr, left, mid, right) {let i = left; // 左子数组的当前索引 let j = mid; // 右子数组的当前索引 let k = 0; // 临时数组的当前索引 let temp = []; // 临时存储合并结果的数组 // 比较左右两个子数组的元素，依次放入 temp 数组 while (i < mid && j < right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++]; } else {temp[k++] = arr[j++]; } } // 将左子数组中剩余的元素放入 temp while (i < mid) {temp[k++] = arr[i++]; } // 将右子数组中剩余的元素放入 temp // 注意：如果 left 子数组已经全部拷贝完，那么 right 子数组剩余的元素会直接拷贝。// 如果 right 子数组已经全部拷贝完，那么这个循环不会执行。while (j < right) {// 也可以写成 for (; j < right; j++) {temp[k++] = arr[j]; } temp[k++] = arr[j++]; } // 将 temp 数组中的元素拷贝回原数组 arr 的对应区间 for (let idx = 0; idx < k; idx++) {arr[left + idx] = temp[idx]; } } // 示例用法 let data = [5, 3, 7, 2, 9, 12, 4]; console.log(" 原始数组：", data); // 输出： 原始数组： [5, 3, 7, 2, 9, 12, 4] mergesort(data, 0, data.length); // 初始调用时，right 为数组长度 console.log(" 排序后数组：", data); // 输出： 排序后数组： [2, 3, 4, 5, 7, 9, 12] let emptyArr = []; mergesort(emptyArr, 0, emptyArr.length); console.log(" 空数组排序后：", emptyArr); // 输出： 空数组排序后： [] let singleArr = [42]; mergesort(singleArr, 0, singleArr.length); console.log(" 单元素数组排序后：", singleArr); // 输出： 单元素数组排序后： [42]总结与注意事项
- 边界条件处理： 在实现递归算法时，对 left 和 right 等索引参数的定义（是包含还是不包含）至关重要。统一采用“左闭右开”区间 [left, right) 是一种推荐的实践，它能简化循环条件和避免越界错误。
- 临时数组回写： merge 函数中将临时数组 temp 的内容复制回原数组 arr 时，务必确保索引的正确性。temp 通常从 0 开始填充，而 arr 的目标区间可能从 left 开始，因此需要进行索引偏移。
- 效率优化： 对于整数除法，使用 位运算符 >> 1 通常比 parseInt() 或 Math.floor()更高效。
- 代码简洁性： 遵循语言习惯，编写逻辑清晰、易于理解的代码。例如，while 循环中可以利用 k ++ 和 i ++ 等后置增量运算符来简化代码。
通过理解和避免这些常见陷阱，开发者可以更自信、更高效地实现归并 排序算法。
