归并排序详解
一、核心思路
归并排序（Merge Sort）是典型的分治算法。我们可以这样理解它的逻辑：
- 快速排序：整个数组有序 = 基准元素有序 + 左侧子数组有序 + 右侧子数组有序。
- 归并排序：整个数组有序 = 左半部分有序 + 右半部分有序 + 两个有序子数组合并。
简单来说，就是把大问题拆解成小问题，解决小问题后，再把结果合并起来。
1. 边界处理
在递归过程中，我们需要先定义好终止条件，避免无效计算：
array == null：空数组无需排序。left == right：只有一个元素时，天然有序，直接返回。left > right：区间非法，直接返回。
2. 合并操作
当递归回到上一层时，左右两个子数组都已经有序了。此时只需要执行一次标准的'双指针合并'操作，将两个有序数组合并为一个更大的有序数组。
3. 算法本质
从底层的最小单元（单个元素）开始，自底向上地不断合并，直到最终形成一个完整的有序数组。
二、代码实现
下面是基于 Java 的完整实现。注意看 merge 函数中的双指针逻辑，这是归并排序的关键。
public static void mergeSort(int[] array) {
if (array == null || array.length < 2) return;
mergeSortFunc(array, 0, array.length - 1);
}
private static void mergeSortFunc(int[] array, int left, int right) {
// 递归终止条件：区间内只有一个元素或非法区间
if (left >= right) return;
int mid = left + ((right - left) >> 1); // 防止溢出的写法
// 1. 递归拆分左边
mergeSortFunc(array, left, mid);
// 2. 递归拆分右边
mergeSortFunc(array, mid + 1, right);
// 3. 合并两个有序区间
merge(array, left, right, mid);
}
private static void merge(int[] array, int left, int right, int mid) {
int s1 = left; // 左区间起始指针
int s2 = mid + 1; // 右区间起始指针
int[] tmpArr = new int[right - left + 1]; // 临时数组用于存储合并结果
int k = 0;
// 当两个区间都有数据时，比较大小放入临时数组
while (s1 <= mid && s2 <= right) {
if (array[s1] <= array[s2]) {
tmpArr[k++] = array[s1++];
} else {
tmpArr[k++] = array[s2++];
}
}
// 将剩余的数据拷贝到临时数组
while (s1 <= mid) {
tmpArr[k++] = array[s1++];
}
while (s2 <= right) {
tmpArr[k++] = array[s2++];
}
// 将临时数组的内容拷回原数组对应位置
for (int i = 0; i < tmpArr.length; i++) {
array[i + left] = tmpArr[i];
}
}
三、递归调用栈解析
理解归并排序，必须理解它的递归过程。这不仅仅是代码的执行，更是内存中栈帧的变化。
1. 执行流程
递归就像剥洋葱。第一次调用进入第二层，第二层等第三层...直到触底（left >= right）。然后开始一层层 return，在回溯的过程中执行合并操作。
2. 栈帧变化
每次函数调用都会在调用栈上压入一个新的栈帧（Stack Frame），包含局部变量、参数和返回地址。
- 向下递归：栈帧不断压入，深度增加。到达最底层时，栈空间占用最大。
- 向上回溯：函数执行完毕弹出栈帧，同时触发合并逻辑。
值得注意的是，在归并排序的二叉树结构中，每一层不仅要处理左边的递归到底再回来，还要处理右边的递归到底再回来。只有当左右都处理完，当前层的栈帧才会弹出。
栈帧空间细节
- 递归函数栈帧：每个栈帧的大小是常数级的。树的高度是
log(n)，所以这部分的空间是O(log n)。 - 合并函数栈帧：
merge函数内部会开辟一个大小为right - left + 1的临时数组。虽然这个数组随着递归层级上升而变大，但它是在栈顶临时开辟，用完即释放。在最顶层调用时，这个临时数组大小为n。
四、复杂度分析
1. 空间复杂度
空间复杂度关注的是执行过程中的最大瞬时占用空间。
- 最底层：递归深度最深，但合并数组很小（接近 0）。总空间 ≈
O(log n)。 - 最顶层：递归深度为 1，但需要合并整个数组，临时数组大小为
n。总空间 ≈n。
在整个过程中，最大的瞬时空间出现在最顶层合并时，因此归并排序的空间复杂度为 O(n)。
2. 时间复杂度
时间复杂度主要取决于合并操作的次数。
- 每层工作量：无论递归到哪一层，所有节点合并数据的总长度都是
n。 - 层数：二叉树的高度是
log(n)。 - 总计：
n * log(n)。
所以，归并排序的时间复杂度稳定为 O(n log n)，无论最好、最坏还是平均情况。
总结：归并排序是一种稳定的排序算法，适合对稳定性有要求且数据量较大的场景。虽然它需要额外的 O(n) 空间，但其时间效率非常可靠。