苏黎世贝勒爷1. 归并排序算法原理与力扣实战指南
作为程序员必备的经典排序算法，归并排序在力扣（LeetCode）算法题库中占据重要地位。我第一次接触这个算法是在解决「合并两个有序链表」问题时，当时就被它分而治之的优雅思路所吸引。本文将结合我在力扣刷题中积累的实战经验，深入解析归并排序的核心原理，并带你用这个算法攻破5道经典力扣题目。
归并排序采用典型的分治策略（Divide and Conquer），其时间复杂度稳定在O(nlogn)，特别适合处理链表排序等场景。与快速排序相比，它虽然需要额外空间，但胜在稳定性——这对解决某些特定问题至关重要。接下来我们将从算法原理、代码实现到力扣实战，全方位掌握这个算法利器。
1.1 分治思想的三步走战略
归并排序的精髓可以概括为三个步骤：
- 分解：将当前区间一分为二，就像切蛋糕一样均匀分割
- 解决：递归排序两个子区间，直到区间长度为1（天然有序）
- 合并：将两个有序子区间合并为一个有序区间
这种分治策略在力扣的许多题目中都有体现。比如在「排序链表」（第148题）中，传统的插入排序会导致O(n²)的时间复杂度，而采用归并排序就能将效率提升到O(nlogn)。
关键提示：归并排序的稳定性体现在——相等元素的相对位置在排序前后不会改变。这个特性在「计算右侧小于当前元素的个数」（第315题）等题目中至关重要。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 归并排序的标准实现
2.1 递归版模板代码
我们先来看最基础的数组排序实现。以下Java代码是我在力扣刷题中总结的通用模板：
java复制public void mergeSort(int[] nums, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2; // 防止溢出
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
private void merge(int[] nums, 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) {
temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
System.arraycopy(temp, 0, nums, left, temp.length);
}
这段代码有几个值得注意的细节：
- 计算mid时采用
left + (right - left)/2而非(left+right)/2，避免整数溢出 - merge操作中使用
<=而非<保证稳定性 - 使用System.arraycopy进行批量数组拷贝，效率高于循环赋值
2.2 迭代版实现技巧
递归虽然直观，但在处理大规模数据时可能引发栈溢出。这时迭代版本就更可靠：
python复制def mergeSort(nums):
size = 1
while size < len(nums):
for left in range(0, len(nums), 2*size):
mid = left + size - 1
right = min(left + 2*size - 1, len(nums)-1)
merge(nums, left, mid, right)
size *= 2
def merge(nums, left, mid, right):
# 合并逻辑与递归版类似
pass
迭代版从底部开始，先两两合并，再四四合并，逐步扩大合并区间。这种实现方式在「K个有序链表合并」（第23题）的解决方案中特别有用。
3. 力扣经典题目实战
3.1 排序链表（第148题）
这道题要求时间复杂度O(nlogn)，空间复杂度O(1)。归并排序的递归实现虽然简单，但空间复杂度是O(logn)。更优解是自底向上的迭代法：
python复制def sortList(head):
if not head or not head.next:
return head
# 计算链表长度
length = 0
p = head
while p:
length += 1
p = p.next
dummy = ListNode(0)
dummy.next = head
size = 1
while size < length:
curr = dummy.next
tail = dummy
while curr:
left = curr
right = split(left, size)
curr = split(right, size)
tail = merge(left, right, tail)
size *= 2
return dummy.next
这个实现的关键点在于：
- split函数将链表从指定位置断开
- merge函数合并两个有序链表并接在tail后面
- 每次合并后更新tail位置
3.2 计算右侧小于当前元素的个数（第315题）
这道hard题目完美展现了归并排序的威力。我们在合并过程中统计逆序对：
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> res = new ArrayList<>();
for (int count : counts) res.add(count);
return res;
}
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, k = 0;
while (left <= mid && right <= end) {
if (nums[indexes[right]] < nums[indexes[left]]) {
newIndexes[k++] = indexes[right++];
rightCount++;
} else {
counts[indexes[left]] += rightCount;
newIndexes[k++] = indexes[left++];
}
}
while (left <= mid) {
counts[indexes[left]] += rightCount;
newIndexes[k++] = indexes[left++];
}
while (right <= end) {
newIndexes[k++] = indexes[right++];
}
System.arraycopy(newIndexes, 0, indexes, start, newIndexes.length);
}
这个解法巧妙之处在于：
- 通过索引数组保持原始位置信息
- 在合并过程中统计右侧较小元素数量
- 时间复杂度O(nlogn)，比暴力解法O(n²)高效得多
3.3 合并K个升序链表（第23题）
这道题可以看作是归并排序的进阶应用。我们可以将K个链表的合并转化为两两合并的过程：
python复制def mergeKLists(lists):
if not lists:
return None
interval = 1
while interval < len(lists):
for i in range(0, len(lists) - interval, interval * 2):
lists[i] = mergeTwoLists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if lists else None
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next
这种解法的时间复杂度是O(NlogK)，其中N是所有节点的总数，K是链表数量。相比逐次合并的O(NK)效率更高。
4. 归并排序的变种与应用
4.1 逆序对问题
归并排序非常适合解决各种逆序对问题。比如在「重要翻转对」（第493题）中，我们需要统计满足nums[i] > 2*nums[j]且i < j的对数：
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 i = left, j = mid + 1;
while (i <= mid) {
while (j <= right && nums[i] > 2L * nums[j]) j++;
count += j - (mid + 1);
i++;
}
merge(nums, left, mid, right);
return count;
}
这个解法在标准归并排序基础上增加了统计步骤，时间复杂度仍然是O(nlogn)。
4.2 区间和的个数（第327题）
这道题要求计算区间和在[lower, upper]范围内的子数组数量。我们可以利用归并排序的思想：
python复制def countRangeSum(nums, lower, upper):
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
return mergeSort(prefix, 0, len(prefix)-1, lower, upper)
def mergeSort(prefix, left, right, lower, upper):
if left >= right:
return 0
mid = (left + right) // 2
count = mergeSort(prefix, left, mid, lower, upper) + \
mergeSort(prefix, mid+1, right, lower, upper)
i = j = mid + 1
for k in range(left, mid + 1):
while i <= right and prefix[i] - prefix[k] < lower:
i += 1
while j <= right and prefix[j] - prefix[k] <= upper:
j += 1
count += j - i
prefix[left:right+1] = sorted(prefix[left:right+1])
return count
这个解法将问题转化为前缀和数组的归并排序问题，巧妙利用了排序后的有序性来高效统计区间和。
5. 常见错误与调试技巧
在力扣刷题过程中，我总结了一些归并排序常见的坑：
- 无限递归：忘记写递归终止条件
left >= right - 索引越界：计算mid时使用
(left+right)/2可能导致整数溢出 - 合并逻辑错误：忘记处理剩余元素，只合并了前半部分
- 空间浪费：每次merge都创建新数组，可以优化为共用临时数组
调试时可以：
- 打印每次递归调用的参数范围
- 可视化合并过程（用小的测试用例）
- 检查合并后的数组是否真的有序
对于链表问题，特别注意：
- 断开链表时要置空next指针
- 合并时注意更新指针位置
- 使用dummy节点简化边界处理
我在解决「排序链表」时就曾因为忘记断开链表而导致死循环，最终通过打印每个子链表的头尾节点才定位到问题。