本文深入探讨了javaScript归并排序（Merge sort）实现中常见的几个关键错误，包括归并操作中临时数组回写时的索引错位、边界参数`right`的语义不一致以及次优的中间点计算方式。通过详细分析问题并提供优化后的代码示例，旨在帮助开发者构建健壮、高效且符合javascript编程习惯的归并排序算法。
理解归并排序的基本原理
归并排序（Merge Sort）是一种高效的、稳定的排序算法，其核心思想是“分而治之”。它将一个大问题分解为若干个小问题，然后将小问题的解合并起来得到大问题的解。具体到排序，就是：
- 分解（Divide）: 将待排序数组递归地分解为两个子数组，直到每个子数组只包含一个元素（单个元素被认为是已排序的）。
- 解决（Conquer）: 对每个子数组进行排序（实际上，分解到单个元素时，这一步是隐式的）。
- 合并（Combine）: 将两个已排序的子数组合并成一个更大的已排序数组。这个合并操作是归并排序的关键。
原始实现中的问题分析
在给定的JavaScript归并排序代码中，存在几个关键问题导致其无法正常工作并产生 undefined 值。
1. 归并操作中临时数组回写时的索引错误
这是导致输出 [undefined, undefined, …, 3, 5] 的直接原因。在 merge 函数的最后一步，将 temp 数组中的排序结果拷贝回原数组 arr 时，使用了错误的索引逻辑：
立即学习“Java免费学习笔记（深入）”；
// 原始错误代码段 for (let i = left; i <= right; i++) { arr[i] = temp[i]; // 错误：temp数组是从索引0开始填充的 }temp 数组是从索引 0 开始填充的，其有效元素范围是 0 到 k-1。然而，上述代码却尝试使用 arr 的原始索引 i（从 left 到 right）来访问 temp 数组。当 left 不为 0 时，temp[left] 可能越界（undefined），或者访问到 temp 中不正确的位置。
修正方案： 正确的回写逻辑应该将 temp 数组中的元素从其起始位置 0 开始，依次拷贝到 arr 数组中从 left 开始的位置。
// 正确的临时数组回写逻辑 for (let idx = 0; idx < k; idx++) { arr[left + idx] = temp[idx]; }这里，idx 用于遍历 temp 数组的有效范围 [0, k-1]，而 left + idx 则确保这些元素被放置到 arr 数组中正确的起始位置。
2. right 参数语义不一致及初始调用错误
在许多编程语言和库中，处理数组或列表的范围时，有两种常见的索引约定：
- 闭区间 [left, right]: left 和 right 都包含在范围内。
- 半开区间 [left, right): left 包含在范围内，而 right 是范围的结束点，但不包含在范围内（即“超尾”索引）。
原始代码的 mergesort 函数内部，循环条件如 i <= mid 和 j <= right 表明 right 被视为闭区间。然而，在初始调用 mergesort(arr, 0, n) 时，n 是数组的长度，这意味着 right 被当做超尾索引（arr.Length）。这种不一致导致：
- 当 right 作为数组长度传入时，arr[right] 会尝试访问数组越界的位置，可能导致 undefined。
- mid 的计算方式也需要与 right 的语义保持一致。
最佳实践： 在JavaScript等语言中，将 right 参数定义为半开区间的“超尾”索引（即不包含在范围内的第一个索引）是更常见和推荐的做法。这与 Array.prototype.slice() 等内置方法的行为一致，并且简化了循环条件（通常从 i <= right 变为 i < right）。
如果采用半开区间语义：
- mergesort(arr, 0, arr.length) 是正确的初始调用。
- mergesort 和 merge 函数内的所有循环条件都应使用 < 而非 <= right 或 <= mid。
- 递归调用 mergesort(arr, left, mid) 和 mergesort(arr, mid, right) 也符合半开区间语义。
3. 中间点计算与冗余拷贝优化
-
中间点 mid 的计算： 原始代码使用 let mid = parseInt((right – left) / 2) + left; 来计算中间点。使用 parseInt 和浮点除法再转换的方式效率较低。 优化： 使用位运算 >> 1 进行整数除法更高效：let mid = left + ((right – left) >> 1);。
-
merge 函数中的冗余拷贝： 原始 merge 函数在主 while 循环结束后，有两个 for 循环用于拷贝剩余元素：
for (; i <= mid; i++) { temp[k] = arr[i]; k++; } for (; j <= right; j++) { temp[k] = arr[j]; k++; }在采用半开区间语义的 merge 逻辑中，如果 i 已经达到 mid，说明左半部分已处理完毕，剩余的元素都在右半部分。如果 j 已经达到 right，说明右半部分已处理完毕，剩余的元素都在左半部分。 一个常见的优化是：当其中一个子数组的所有元素都已拷贝到 temp 后，如果另一个子数组还有剩余元素，这些剩余元素本身就已经是排序好的，并且它们在原数组中的位置相对于已合并的部分是正确的。因此，只需将未完全拷贝的那个子数组的剩余元素拷贝到 temp 即可。在某些实现中，甚至可以省略拷贝右半部分剩余元素到 temp 的步骤，因为它们在原数组中的相对顺序已经正确，后续的 temp 回写操作会覆盖 arr[left] 到 arr[left+k-1] 的部分，而 arr[j] 之后的元素保持不变。
改进后的归并排序实现
综合上述分析和优化，以下是修正并遵循JavaScript惯例的归并排序实现：
/** * 归并排序主函数 * @param {Array<number>} arr 待排序数组 * @param {number} left 数组范围的起始索引 (包含) * @param {number} right 数组范围的结束索引 (不包含, 超尾) */ function mergesort(arr, left, right) { // 当子数组长度大于1时才需要排序 if (right - left > 1) { // 计算中间索引，使用位运算进行高效的整数除法 // mid 将是左半部分的超尾索引，也是右半部分的起始索引 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, // 左子数组的当前索引 j = mid, // 右子数组的当前索引 k = 0; // 临时数组的当前索引 let temp = []; // 临时数组用于存储合并结果 // 比较并合并左右两个子数组的元素，直到其中一个子数组遍历完毕 while (i < mid && j < right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 将左半部分剩余元素拷贝到临时数组 // 如果左半部分还有剩余，说明右半部分已经全部拷贝 while (i < mid) { temp[k++] = arr[i++]; } // 注意：如果右半部分有剩余（即 j < right）， // 它们已经相对有序地存在于原数组中，并且在合并后的结果中， // 这些元素将位于 temp 数组回写操作覆盖范围之外， // 或者它们会被 temp 数组的