归并排序通过分治法将数组递归拆分为单个元素后，再逐层合并为有序数组，其核心是分解与合并过程，JavaScript实现包括递归分割和双指针合并两个有序子数组。
归并排序是一种典型的分治算法，通过将数组不断拆分，再逐层合并，最终实现有序排列。它的核心思想是“分而治之”：把一个大问题分解成多个小问题分别解决，再把结果合并起来。
归并排序的基本原理
归并排序分为两个阶段：分解和合并。
- 分解：将数组从中间一分为二，递归地对左右两部分继续分解，直到每个子数组只有一个元素（单个元素天然有序）。
- 合并：将两个有序的子数组合并成一个新的有序数组，通过比较元素大小依次放入临时数组中，最后写回原数组。
这个过程保证了每次合并时输入的两个子数组都是有序的，因此可以高效地完成整体排序。
JavaScript实现归并排序
下面是一个清晰、可读性强的归并排序实现：
立即学习“Java免费学习笔记（深入）”；
function mergeSort(arr) {
// 基本情况：数组长度小于等于1时直接返回
if (arr.length <= 1) return arr;
// 分割数组
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// 合并两个有序数组
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0, j = 0;
// 比较两个数组的元素，按顺序推入结果数组
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// 将剩余元素合并
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
使用示例：
const unsortedArray = [64, 34, 25, 12, 22, 11, 90]; const sortedArray = mergeSort(unsortedArray); console.log(sortedArray); // [11, 12, 22, 25, 34, 64, 90]
归并排序的特点与适用场景
归并排序有以下几个显著优点：
- 稳定性好：相等元素的相对位置不会改变，适合需要稳定排序的场景。
- 时间复杂度稳定：无论最好、最坏还是平均情况，时间复杂度都是 O(n log n)。
- 适用于大数据量：在处理大规模数据时性能表现可靠。
但也有一些缺点：
- 空间复杂度较高：需要额外的 O(n) 空间来存储临时数组。
- 不是原地排序：不像快速排序那样可以在原数组上操作。
因此，在内存受限或追求极致性能的场景中可能不是最优选择，但在大多数通用排序需求中非常可靠。
基本上就这些。归并排序逻辑清晰，实现不难，是理解分治思想的绝佳例子。掌握它，对深入学习算法很有帮助。
