本文深入探讨了javascript归并排序实现中常见的索引处理错误、边界条件问题以及性能优化点。通过分析一个典型的错误代码示例，文章详细解释了在`merge`函数中将临时数组数据复制回原数组时的索引错位、不当的中间索引计算方式，以及数组右边界参数定义不一致的问题。最终，提供了一个遵循“左闭右开”区间原则且经过优化的归并排序实现，旨在帮助开发者构建更健壮、高效的排序算法。
归并排序概述
归并排序（Merge Sort）是一种基于分治思想的高效稳定排序算法。其基本思想是将一个大的无序数组递归地分成两个较小的子数组，直到子数组只包含一个元素（自然有序），然后将这些有序的子数组两两合并，最终得到一个完全有序的数组。这个过程的核心在于merge（合并）操作，它负责将两个已排序的子数组合并成一个更大的有序数组。
初始问题代码分析
我们首先来看一个常见的归并排序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++) { // 错误点1
arr[i] = temp[i]; // 错误点1
}
}
let arr = [ 5, 3, 7, 2, 9, 12, 4 ];
n = arr.length;
mergesort(arr, 0, n); // 错误点2这段代码在执行后，可能会输出类似 [undefined, undefined, undefined, undefined, undefined, undefined, 3, 5] 的结果，表明排序未能正确完成，并且数组中出现了undefined值。这通常是由于索引越界或数据未正确复制导致的。
错误识别与修正
通过仔细分析，我们可以发现上述代码中存在以下几个关键问题：
立即学习“Java免费学习笔记（深入）”；
1. merge函数中数据回写错误
问题描述： 在merge函数的最后一步，将临时数组temp中的数据复制回原数组arr时，使用了相同的索引i来访问arr和temp。
// 原始错误代码片段
for (let i = left; i <= right; i++) {
arr[i] = temp[i];
}temp数组是从索引0开始填充的，其有效元素范围是[0, k-1]。而arr数组的目标复制范围是从left到right。直接使用i作为temp的索引会导致temp[i]在i > k-1时访问到undefined，或者在left不为0时，temp[left]可能访问到错误的数据。
修正方案： 需要使用两个不同的索引变量，一个用于遍历temp数组（从0开始），另一个用于确定在arr数组中的起始位置（从left开始）。
// 修正后的代码片段
for (let idx = 0; idx < k; idx++) {
arr[left + idx] = temp[idx];
}2. 初始调用中的右边界参数
问题描述： 初始调用mergesort(arr, 0, n)时，将n（即arr.length）作为right参数传递。然而，mergesort函数内部的right参数被期望为数组的最后一个元素的索引，即n-1。这种不一致的语义会导致right参数超出实际数组范围。
修正方案： 如果我们坚持right为最后一个元素的索引的语义，那么初始调用应为mergesort(arr, 0, n - 1)。然而，更推荐的做法是采用“左闭右开”的区间语义，这将在后续的优化实践中详细说明。
3. 中间索引mid的计算方式
问题描述： let mid = parseInt((right - left) / 2) + left; 这种计算mid的方式虽然在大多数情况下能得到正确结果，但parseInt操作涉及到字符串转换，效率较低。
优化方案： 在JavaScript中，更高效且推荐的整数除法方式是使用位运算符>> 1（右移一位，相当于除以2并向下取整）。
// 优化后的mid计算 let mid = left + ((right - left) >> 1);
4. merge函数中剩余元素的复制
问题描述： 原始merge函数在主while循环结束后，有两段for循环用于复制剩余元素：
// 原始代码片段
for (; i <= mid; i++) {
temp[k] = arr[i];
k++;
}
for (; j <= right; j++) {
temp[k] = arr[j];
k++;
}这些循环将arr中未处理的元素复制到temp中。虽然功能上正确，但当采用“左闭右开”的区间语义并优化merge逻辑后，这部分可以更简洁地表达。
优化实践：采用“左闭右开”区间语义
在许多编程语言和算法实现中，数组/区间操作常采用“左闭右开”的区间表示法，即[left, right)，表示从left索引开始（包含）到right索引结束（不包含）。这种约定可以简化边界条件的处理，尤其是在递归和循环中。
下面是基于“左闭右开”语义的优化版归并排序实现：
/**
* 归并排序主函数
* @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 (如果有的话)
// 注意：如果左半部分有剩余，右半部分不可能有；反之亦然。
// 所以这里的两个while循环只会执行其中一个。
while (j < right) {
temp[k++] = arr[j++];
}
// 将temp数组中的有序元素复制回原数组的对应位置
// 这里的i重新用作temp数组的索引，从0开始
for (let idx = 0; idx < k; idx++) {
arr[left + idx] = temp[idx];
}
}
// 示例调用
let data = [ 5, 3, 7, 2, 9, 12, 4 ];
mergesort(data, 0, data.length); // 初始调用：从索引0到数组长度(不包含)
console.log(data); // 输出: [2, 3, 4, 5, 7, 9, 12]优化版代码的特点：
- “左闭右开”区间语义： mergesort(arr, left, right) 和 merge(arr, left, mid, right) 中的 right 参数都表示子数组结束位置的下一个索引，不包含该索引处的元素。这使得right - left可以直接表示子数组的长度。
- mid计算优化： 使用 left + ((right - left) >> 1) 替代 parseInt，提高了效率。
- mergesort递归调用： 调整为 mergesort(arr, left, mid) 和 mergesort(arr, mid, right)，与“左闭右开”语义保持一致。
-
merge函数简化：
- while (i < mid && j < right)：循环条件精确反映了左右子数组的有效范围。
- while (i < mid) 和 while (j < right)：这两个循环用于处理某个子数组可能提前遍历完的情况，将另一个子数组中剩余的元素直接复制到temp。由于两个子数组本身已经有序，直接复制即可。
- for (let idx = 0; idx < k; idx++) { arr[left + idx] = temp[idx]; }：修正了数据回写时的索引问题，确保temp中的元素正确地复制回arr的指定位置。
- 初始调用： mergesort(data, 0, data.length)，直接使用arr.length作为右边界，符合“左闭右开”语义。
总结与注意事项
实现归并排序时，以下几点是需要特别注意的：
- 索引管理： 这是归并排序中最容易出错的地方。务必清晰定义每个参数（left, mid, right）的含义（是包含还是不包含），并在整个函数中保持一致。推荐使用“左闭右开”区间[left, right)，它能简化很多边界条件判断。
- mid计算： 使用位运算>> 1进行整数除法，避免parseInt带来的性能开销。
- merge逻辑： 确保merge函数能够正确地将两个已排序的子数组合并成一个，并且最终将合并结果准确无误地复制回原数组的正确位置。特别是从临时数组回写数据时，要处理好索引的偏移。
- 空间复杂度： 归并排序通常需要额外的O(N)空间来存储临时数组temp。在某些场景下，如果内存是严格限制的，可能需要考虑原地归并排序等更复杂的变体，但实现难度会大大增加。
通过理解和应用这些修正与优化实践，开发者可以构建出健壮、高效且符合行业最佳实践的JavaScript归并排序实现。
