本文深入探讨了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进行整数除法，这是一种更高效且常用的方法。
let mid = left + ((right - left) >> 1); // 等同于 Math.floor((right - left) / 2) + left
问题点四：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} 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} 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++等后置增量运算符来简化代码。
通过理解和避免这些常见陷阱，开发者可以更自信、更高效地实现归并排序算法。
