js实现归并
归并排序原理
归并排序是一种分治算法，通过递归将数组拆分为最小单元（单个元素），再逐步合并有序子数组。核心思想是“分而治之”，时间复杂度为O(n log n)，空间复杂度为O(n)。
递归实现
递归法通过不断二分数组直至长度为1，再合并有序子数组：
function mergeSort(arr) {
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++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}迭代实现
非递归版本使用循环模拟分治过程，避免调用栈过深：
function mergeSort(arr) {
let step = 1;
const n = arr.length;
while (step < n) {
let l = 0;
while (l < n) {
const m = Math.min(l + step, n);
const r = Math.min(l + 2 * step, n);
merge(arr, l, m, r);
l += 2 * step;
}
step *= 2;
}
return arr;
}
function merge(arr, start, mid, end) {
const temp = [...arr];
let i = start, j = mid, k = start;
while (i < mid && j < end) {
arr[k++] = temp[i] <= temp[j] ? temp[i++] : temp[j++];
}
while (i < mid) arr[k++] = temp[i++];
}性能优化点
- 小数组切换插入排序：当子数组长度较小时（如<15），插入排序更高效
- 避免重复分配内存：预分配临时数组复用
- 边界检查优化：提前终止已有序数组的合并
复杂度分析
- 时间：始终为O(n log n)，不受输入数据影响
- 空间：需要额外O(n)存储空间
- 稳定性：是稳定排序算法（相等元素不改变相对位置）
使用示例
const arr = [3, 44, 38, 5, 47, 15];
console.log(mergeSort(arr)); // [3, 5, 15, 38, 44, 47]
