本文深入探讨了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函数中冗余的元素复制
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++等后置增量运算符来简化代码。
通过理解和避免这些常见陷阱，开发者可以更自信、更高效地实现归并排序算法。