香香甜甜圈1. 归并排序与力扣刷题的完美结合
归并排序作为分治算法的经典代表，在力扣（LeetCode）算法题库中占据着重要地位。我第一次在力扣上遇到归并排序相关题目时，就被它优雅的递归实现和稳定的O(nlogn)时间复杂度所吸引。对于准备技术面试的开发者来说，掌握归并排序不仅能解决特定类型的排序问题，更能培养分治思维，这对解决更复杂的算法问题大有裨益。
力扣平台上有大量基于归并排序变种的题目，从最简单的数组排序到复杂的链表操作，再到解决逆序对等衍生问题。这些题目往往考察的不仅是排序本身，更是对分治思想的理解和应用能力。在实际面试中，面试官也特别喜欢用归并排序的变种题来考察候选人的算法基本功。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 归并排序核心原理深度解析
2.1 分治思想的三步走战略
归并排序的核心在于"分而治之"的策略，这正好对应着力扣上很多分治类题目的解题思路。具体实现可以分为三个关键步骤：
-
分解阶段：将当前数组从中间位置一分为二，递归地对左右两个子数组进行排序。这个过程会一直持续到子数组长度为1（天然有序）为止。在力扣的"排序数组"（第912题）中，这个分解过程就是解决问题的起点。
-
解决阶段：当子数组被分解到最小单位后，开始逐层向上解决。这个阶段实际上是在递归的回溯过程中完成的。
-
合并阶段：这是归并排序最具特色的部分 - 将两个已排序的子数组合并成一个有序数组。合并时需要额外的空间来暂存结果，这也是归并排序空间复杂度为O(n)的原因。
java复制// 典型的归并排序Java实现框架
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 防止整数溢出
mergeSort(arr, left, mid); // 递归排序左半部分
mergeSort(arr, mid + 1, right); // 递归排序右半部分
merge(arr, left, mid, right); // 合并两个有序子数组
}
}
2.2 关键合并操作实现细节
合并操作是归并排序效率的保证，也是力扣相关题目中最常考察的环节。以力扣第88题"合并两个有序数组"为例，合并过程需要：
- 创建临时数组存放合并结果（原地合并变种除外）
- 使用双指针分别遍历两个子数组
- 比较指针所指元素，将较小的放入结果数组
- 当某子数组遍历完后，将另一子数组剩余部分直接追加
java复制void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
注意：在力扣编程题中，处理数组边界时要特别小心。比如计算mid时使用left + (right - left)/2而不是(left + right)/2，可以避免整数溢出问题。
3. 力扣经典题目实战解析
3.1 基础应用：排序数组（LeetCode 912）
这是最直接的归并排序应用题，要求对整数数组进行升序排序。虽然题目可以用任何排序算法解决，但选择归并排序有几个优势：
- 稳定的O(nlogn)时间复杂度，适合大规模数据
- 稳定的排序（相等元素相对位置不变）
- 递归实现代码清晰，易于理解和调试
在实际实现时，我建议：
- 将递归终止条件设为left >= right而非left == right，可以避免单元素数组的特殊处理
- 临时数组可以在类级别创建一次，避免每次merge都new新数组，减少GC压力
3.2 进阶应用：数组中的逆序对（LeetCode 剑指 Offer 51）
这道题要求统计数组中的逆序对数量，是归并排序的经典变种。关键在于在合并过程中统计逆序对：
- 当右子数组元素小于左子数组元素时，意味着左子数组当前元素及其后所有元素都与该右子数组元素构成逆序对
- 逆序对数量增加量为mid - i + 1（i是左子数组当前指针）
java复制public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length - 1);
}
private int mergeSort(int[] nums, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
count += mid - i + 1; // 关键统计点
temp[k++] = nums[j++];
}
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
System.arraycopy(temp, 0, nums, left, temp.length);
return count;
}
3.3 链表排序：排序链表（LeetCode 148）
这道题要求对链表进行O(nlogn)时间复杂度的排序，且使用常数级空间复杂度（递归栈空间不算）。归并排序是解决链表排序问题的最佳选择：
- 使用快慢指针找到链表中点
- 递归排序左右两部分链表
- 合并两个已排序链表
java复制public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 != null ? l1 : l2;
return dummy.next;
}
提示：链表归并排序的空间复杂度主要是递归调用栈的O(logn)，比数组版的O(n)更优。这也是为什么链表排序常选用归并而非快排。
4. 归并排序的力扣刷题技巧
4.1 常见变种与识别特征
在力扣刷题时，以下特征可能暗示需要使用归并排序或分治思想：
- 问题可以分解为相似的子问题（如排序、统计）
- 子问题的解可以合并为原问题的解
- 题目要求O(nlogn)时间复杂度
- 涉及逆序对、区间统计等问题
- 处理链表排序等非连续内存数据结构
4.2 调试与性能优化技巧
-
递归深度问题：对于极大数组，递归可能导致栈溢出。可以改为迭代实现（自底向上归并），但会牺牲代码可读性。
-
空间优化：
- 可以在类级别维护一个全局临时数组，避免频繁创建
- 对于链表问题，天然不需要额外空间（除了递归栈）
-
边界条件：
- 空数组/单元素数组处理
- 数组越界检查（特别是mid计算）
- 链表的中点分割要确保断开连接
-
稳定性保持：
- 在merge时，对于相等元素应优先取左子数组元素
- 比较条件使用<=而非<
4.3 与其他算法的比较选择
虽然归并排序在很多场景表现出色，但在力扣刷题时也要根据具体情况选择：
-
快速排序：
- 平均O(nlogn)，最坏O(n²)
- 原地排序，空间O(1)
- 不稳定排序
- 适合大多数随机数组排序
-
堆排序：
- 最差O(nlogn)
- 原地排序
- 不稳定
- 适合需要部分排序或实时排序的场景
-
归并排序：
- 稳定O(nlogn)
- 需要额外O(n)空间
- 稳定排序
- 适合链表排序、需要稳定性的场景
5. 高频面试题精讲
5.1 计算右侧小于当前元素的个数（LeetCode 315）
这道题是逆序对问题的升级版，要求对每个元素统计其右侧比它小的元素数量。使用归并排序的思路：
- 对数组进行归并排序，但在排序过程中需要记录每个元素的原下标
- 在合并时，当右子数组元素被选中时，更新左子数组当前及其后元素的计数
- 需要使用索引数组来跟踪元素原始位置
java复制public List<Integer> countSmaller(int[] nums) {
int[] indexes = new int[nums.length];
for (int i = 0; i < nums.length; i++) indexes[i] = i;
int[] counts = new int[nums.length];
mergeSort(nums, indexes, counts, 0, nums.length - 1);
List<Integer> result = new ArrayList<>();
for (int count : counts) result.add(count);
return result;
}
private void mergeSort(int[] nums, int[] indexes, int[] counts, int start, int end) {
if (start >= end) return;
int mid = start + (end - start) / 2;
mergeSort(nums, indexes, counts, start, mid);
mergeSort(nums, indexes, counts, mid + 1, end);
merge(nums, indexes, counts, start, end);
}
private void merge(int[] nums, int[] indexes, int[] counts, int start, int end) {
int mid = start + (end - start) / 2;
int left = start, right = mid + 1;
int[] newIndexes = new int[end - start + 1];
int rightCount = 0, index = 0;
while (left <= mid && right <= end) {
if (nums[indexes[right]] < nums[indexes[left]]) {
newIndexes[index] = indexes[right];
rightCount++;
right++;
} else {
newIndexes[index] = indexes[left];
counts[indexes[left]] += rightCount;
left++;
}
index++;
}
while (left <= mid) {
newIndexes[index] = indexes[left];
counts[indexes[left]] += rightCount;
left++;
index++;
}
while (right <= end) {
newIndexes[index++] = indexes[right++];
}
System.arraycopy(newIndexes, 0, indexes, start, newIndexes.length);
}
5.2 区间和的个数（LeetCode 327）
这道题要求统计区间和在[lower, upper]范围内的子数组数量。使用归并排序的思路：
- 计算前缀和数组
- 对前缀和数组进行归并排序
- 在合并前统计满足条件的区间数量
java复制public int countRangeSum(int[] nums, int lower, int upper) {
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
return mergeSort(prefixSum, 0, prefixSum.length - 1, lower, upper);
}
private int mergeSort(long[] prefixSum, int left, int right, int lower, int upper) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int count = mergeSort(prefixSum, left, mid, lower, upper)
+ mergeSort(prefixSum, mid + 1, right, lower, upper);
int i = mid + 1, j = mid + 1;
for (int k = left; k <= mid; k++) {
while (i <= right && prefixSum[i] - prefixSum[k] < lower) i++;
while (j <= right && prefixSum[j] - prefixSum[k] <= upper) j++;
count += j - i;
}
merge(prefixSum, left, mid, right);
return count;
}
private void merge(long[] arr, int left, int mid, int right) {
long[] temp = new long[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
6. 归并排序的非递归实现
虽然递归实现简洁易懂，但在力扣编程题中，有时需要考虑非递归实现以避免栈溢出问题。自底向上的归并排序是很好的选择：
- 从大小为1的子数组开始，两两合并
- 每次合并后将子数组大小翻倍
- 重复直到整个数组有序
java复制public void mergeSortIterative(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
for (int size = 1; size < n; size *= 2) {
for (int left = 0; left < n - size; left += 2 * size) {
int mid = left + size - 1;
int right = Math.min(left + 2 * size - 1, n - 1);
merge(arr, left, mid, right, temp);
}
}
}
private void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, left, arr, left, right - left + 1);
}
这种实现方式特别适合处理超大规模数据，避免了递归的栈溢出风险。在力扣的编程题中，如果遇到特别大的测试用例导致递归版本栈溢出，可以尝试改用这种迭代实现。