LeetCode 补充题 5. 手撕归并排序
题目描述
给定整数数组
nums，请将其按非递减顺序排列并返回，所有元素及其重复次数都要保留。本补充题沿用力扣「排序数组」的输入输出，要求手动实现归并排序，不能直接调用内置排序函数。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
-
1 <= nums.length <= 5 * 10^4。 -
-5 * 10^4 <= nums[i] <= 5 * 10^4。 - 力扣原题要求 O(n log n) 时间，并尽量减少额外空间。
题意分析
手动实现归并排序，将整数数组按从小到大的顺序排列并返回。重复值要完整保留，负数也按通常的数值大小比较，不调用现成的排序函数。
本题的重点是实现“拆分子问题，再合并有序结果”的排序过程。下面的实现把最终结果写回原数组，同时借助一个等长辅助数组完成合并；修改原数组不代表只使用常数额外空间。
解法：递归分治归并排序
核心思路
[!blue]
一次把整个无序区间排好不容易，但两个已经有序的区间可以线性合并。因此先把当前区间分成两半，分别排序，再合并它们。持续拆分到空区间或单元素区间时，它们本身就有序，递归自然结束。
定义
mergeSort(left, right)的作用为：返回时，原数组闭区间[left, right]已经升序排列，且其中元素一个不少、一个不多。左右递归调用分别保证[left, mid]和[mid + 1, right]有序，当前层只需完成合并。合并时，
i、j分别指向左右两段尚未处理的首元素，idx指向辅助数组的下一个写入位置。因为每段内部有序，全部未处理元素中的最小值一定是nums[i]、nums[j]中较小的那个；把它写入temp[idx]并移动对应指针，就能让已写入部分一直保持有序。相等时先取左侧，使相等元素维持原有先后顺序，得到稳定排序。一侧耗尽后，另一侧的剩余元素本来就有序，也不会小于已经写入的元素，可以直接依次追加。最后把
temp[left..right]写回原数组，当前层便满足返回时区间有序的约定，上层也能继续正确合并。不能在当前这套双指针流程中直接覆盖
nums：写入较小值时可能覆盖还没读出的元素。辅助数组隔开了读取与写入；它在入口只创建一次，各递归调用复用自己的区间，既不丢数据，也避免反复分配。
解题步骤
- 创建与输入等长的辅助数组
temp，从闭区间[0, n - 1]开始排序。- 当
left >= right时返回；否则计算中点，递归排序[left, mid]和[mid + 1, right]。- 左右两段都有序后，用两个指针比较当前值，将较小值写入
temp；相等时先写左侧值。- 一侧耗尽后，将另一侧的所有剩余元素追加到
temp。- 将当前合并区间完整写回
nums；最外层递归结束后返回原数组。
代码实现
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]
}
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(n\log n)$。区间每次近似减半，共有 $O(\log n)$ 层；每层合并和写回合计处理 $n$ 个元素，输入原有顺序不影响这个数量级。
- 辅助空间复杂度：$O(n)$。共享数组占 $O(n)$，递归栈占 $O(\log n)$，不会为每一层再分配一整份数组。
关键点总结
[!green]
- 递归返回时要保证原数组的当前区间有序，合并建立在两个子区间已经有序的基础上。
- 每次只需比较两侧尚未处理的最小值，就能找到下一个全局最小值。
- 辅助数组避免覆盖未读数据，相等时先取左值保证稳定性。
易错点总结
[!yellow]
- 递归出口只写
left > right，会让单元素区间继续递归，规模无法缩小；应使用left >= right。- 右半必须从
mid + 1开始，若仍从mid开始，会与左半重叠，并可能产生无法终止的递归。- 当前合并流程不能直接把结果写进
nums，否则可能覆盖尚未读取的原元素。- 一侧耗尽后，另一侧剩余元素仍必须全部搬完；也要把合并结果写回当前区间，不能留在辅助数组里就返回。
- 相等时若优先取右值，数值仍能排成有序，但会改变相等元素的原有先后顺序，失去稳定性。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 148. 排序链表 | 中等 | 链表归并排序也先分治再合并，本题用共享数组缓存，链表通过指针重接。 |
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 归并过程中还能批量统计跨左右两区的逆序对，本题只完成排序。 |