LeetCode 补充题 5. 手撕归并排序
目录
题目描述
题意分析
题目要求把一个整数数组升序排列，且必须手写归并排序——调用语言内置的排序函数是被明确禁止的，因为面试官要考察的正是排序算法本身的实现功底。
题面对应 LeetCode 912，数组长度可达 $5 \times 10^4$，元素范围 $[-5 \times 10^4, 5 \times 10^4]$ 且可能大量重复。这个规模是一个信号：$O(n^2)$ 的冒泡、插入排序会超时，必须给出 $O(n \log n)$ 级别的做法。
归并排序有两个招牌属性，也是它常被指定手撕的原因：其一，它是稳定排序——相等元素排序后保持原有相对次序，这在「按多个键先后排序」的业务场景里是硬需求；其二，它的 $O(n \log n)$ 是最坏情况保证，不像快速排序在退化输入下会掉到 $O(n^2)$。代价则是需要 $O(n)$ 的额外空间，这正是归并与快排之间「时间下界稳 vs 原地省空间」的经典取舍。
边界方面：空数组和单元素数组天然有序，递归到长度为 1 的区间就应停止。
解法：递归分治归并排序
核心思路
问题关键：两个有序区间可以用双指针在 $O(n)$ 时间内合并。归并排序先不断二分，直到单元素区间天然有序，再自底向上合并，因此每层工作量都是线性的。
为什么选归并排序：它能稳定地保证最坏 $O(n \log n)$，适合题目规模。代价是数组合并时需要 $O(n)$ 辅助空间；相比之下，快排通常原地，但最坏会退化为 $O(n^2)$。
不变量与正确性：
mergeSort(left, right)返回时，nums[left..right]已有序。合并时临时数组中的元素始终有序，两个指针之前的元素都已放到正确位置；每次取当前较小值即可维持该性质。相等时优先取左侧，才能保持稳定性。
解题步骤
- 在入口创建与原数组等长的
temp，所有合并共用。- 对闭区间
[left, right]取中点，递归排序[left, mid]和[mid + 1, right]；区间长度不超过 1 时返回。- 用
i、j分别扫描左右有序区间，每次把较小值写入temp；相等时取左值。- 将尚未耗尽的一侧直接追加到
temp。- 把
temp[left..right]写回nums，恢复递归函数的区间有序不变量。例如
[5,2,3,1]先得到两个有序段[2,5]、[1,3]，最后依次取1、2、3、5，合并为[1,2,3,5]。
代码实现
class Solution {
public int[] sortArray(int[] nums) {
int[] temp = new int[nums.length];
mergeSort(nums, temp, 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] nums, int[] temp, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(nums, temp, left, mid);
mergeSort(nums, temp, mid + 1, right);
merge(nums, temp, left, mid, right);
}
private void merge(int[] nums, int[] temp, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int idx = left;
while (i <= mid && j <= right) {
// 相等时优先取左侧元素，保持归并排序稳定性。
if (nums[i] <= nums[j]) {
temp[idx++] = nums[i++];
} else {
temp[idx++] = nums[j++];
}
}
while (i <= mid) {
temp[idx++] = nums[i++];
}
while (j <= right) {
temp[idx++] = nums[j++];
}
for (int k = left; k <= right; k++) {
nums[k] = temp[k];
}
}
}
func sortArray(nums []int) []int {
temp := make([]int, len(nums))
mergeSort(nums, temp, 0, len(nums)-1)
return nums
}
func mergeSort(nums []int, temp []int, left int, right int) {
if left >= right {
return
}
mid := left + (right-left)/2
mergeSort(nums, temp, left, mid)
mergeSort(nums, temp, mid+1, right)
merge(nums, temp, left, mid, right)
}
func merge(nums []int, temp []int, left int, mid int, right int) {
i := left
j := mid + 1
idx := left
for i <= mid && j <= right {
if nums[i] <= nums[j] {
// 相等时先放左侧，排序过程保持稳定。
temp[idx] = nums[i]
i++
} else {
temp[idx] = nums[j]
j++
}
idx++
}
for i <= mid {
temp[idx] = nums[i]
i++
idx++
}
for j <= right {
temp[idx] = nums[j]
j++
idx++
}
for k := left; k <= right; k++ {
nums[k] = temp[k]
}
}
复杂度分析
- 时间复杂度：$O(n \log n)$。共有 $O(\log n)$ 层，每层合并的总元素数为
n。- 空间复杂度：$O(n)$。辅助数组占 $O(n)$，递归栈占 $O(\log n)$。
关键点总结
- 递归函数的契约是「返回时当前区间有序」，合并必须建立在两个子区间有序之上。
<=时先取左值保证稳定；写成<虽仍能排好整数，却会破坏相等元素的原始顺序。- 临时数组只在入口分配一次，避免每次合并重复申请内存。
- 若面试官追问链表排序：归并可通过改指针完成合并，不需要数组式的 $O(n)$ 缓冲区。
易错点总结
- 递归出口写成
left > right：单元素区间不会停止，最终栈溢出；应为left >= right。- 右区间仍从
mid开始：如[2,1]的递归规模不再缩小；右区间必须是[mid + 1, right]。- 直接向
nums合并：[3,4,1,2]中写入右侧的1会覆盖尚未处理的3，必须先写入缓冲区。- 忘记搬运某一侧剩余元素：会保留临时数组中的旧值或默认值。
- 使用
<选择左值：排序结果仍有序，但[(2,a),(1,x),(2,b)]会让两个 2 的相对次序颠倒，失去稳定性。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 912. 排序数组 | 中等 | 本题原题，也可用快排、堆排作答并对比取舍 |
| 148. 排序链表 | 中等 | 归并思想搬到链表，用快慢指针找中点、改指针原地合并 |
| LCR 077. 排序链表 | 中等 | 148 的镜像题，可练习自底向上迭代归并省递归栈 |
| 21. 合并两个有序链表 | 简单 | 单独抽出「合并两个有序段」这一子过程 |
| 88. 合并两个有序数组 | 简单 | 有序合并的数组版，考察从后往前避免覆盖的指针方向 |
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 在归并的合并阶段顺带统计跨区间逆序对 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 归并计数进阶，需要携带下标做索引归并 |