1. 归并排序算法精要
归并排序（Merge Sort）作为分治算法的经典实现，其核心思想是将数组递归拆分为最小单元后有序合并。我在处理力扣（LeetCode）数组类问题时，发现超过60%的题目都可以通过归并思想或其变种解决。不同于快速排序的原地交换，归并排序需要O(n)的额外空间，但稳定性和可预测的时间复杂度（始终为O(nlogn)）使其成为面试中的高频考点。
算法实现的关键在于三个核心操作：
- 分割：将当前数组平分为左右两部分，递归执行直到子数组长度为1
- 合并：创建临时数组，按序填充左右子数组中的较小元素
- 回写：将排序后的临时数组内容复制回原数组
实际编码时常见误区：在合并阶段未正确处理剩余元素。建议使用双指针法，当某侧指针越界时直接批量复制另一侧剩余元素。
2. 力扣典型题目解析
2.1 基础模板题（#912 排序数组）
这是最直接的归并排序应用题，但力扣的测试用例会刻意包含极端情况。我的AC代码中特别处理了两个边界条件：
python复制def mergeSort(nums):
if len(nums) <= 1: # 递归终止条件
return nums
mid = len(nums) // 2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
return merge(left, right)
def merge(left, right):
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # 保持稳定性
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res.extend(left[i:]) # 处理剩余元素
res.extend(right[j:])
return res
2.2 进阶应用题（#493 翻转对）
这道hard题目要求统计重要翻转对（i < j且nums[i] > 2*nums[j]），常规暴力解法O(n²)会超时。通过改造归并排序，可以在O(nlogn)时间内解决：
- 分治阶段：递归统计左右子数组内部的翻转对
- 合并前处理：对已排序的子数组，用双指针统计跨子数组的翻转对
- 常规合并：执行标准归并操作
python复制def reversePairs(nums):
def mergeSort(l, r):
if l >= r:
return 0
mid = (l + r) // 2
count = mergeSort(l, mid) + mergeSort(mid + 1, r)
# 统计跨子数组翻转对
j = mid + 1
for i in range(l, mid + 1):
while j <= r and nums[i] > 2 * nums[j]:
j += 1
count += j - (mid + 1)
nums[l:r+1] = sorted(nums[l:r+1]) # Python内置TimSort优化
return count
return mergeSort(0, len(nums) - 1)
2.3 链表排序（#148 排序链表）
归并排序是链表排序的最优解，因为：
- 链表不支持随机访问，难以实现快速排序的分区操作
- 归并的O(1)空间复杂度（递归栈除外）适合链表特性
关键改造点：
- 快慢指针找中点：代替数组的随机访问
- 断链操作：将链表从中间断开
- 链表合并：无需额外空间，直接修改节点指针
python复制def sortList(head):
if not head or not head.next:
return head
# 快慢指针找中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 断链并递归
mid, slow.next = slow.next, None
left = sortList(head)
right = sortList(mid)
# 合并有序链表
dummy = ListNode(0)
p = dummy
while left and right:
if left.val < right.val:
p.next = left
left = left.next
else:
p.next = right
right = right.next
p = p.next
p.next = left if left else right
return dummy.next
3. 归并排序的六种变式技巧
3.1 逆序数统计（#315 计算右侧小于当前元素的个数）
本质是统计每个元素右侧比它小的元素个数。在合并过程中，当右子数组元素被选中时，可立即计算其对左子数组剩余元素的贡献值：
python复制def countSmaller(nums):
res = [0] * len(nums)
def mergeSort(enums):
if len(enums) <= 1:
return enums
mid = len(enums) // 2
left = mergeSort(enums[:mid])
right = mergeSort(enums[mid:])
# 逆序统计
i = j = 0
while i < len(left) and j < len(right):
if left[i][1] <= right[j][1]:
res[left[i][0]] += j
i += 1
else:
j += 1
while i < len(left):
res[left[i][0]] += j
i += 1
return sorted(enums, key=lambda x: x[1]) # 简化实现
mergeSort(list(enumerate(nums)))
return res
3.2 区间合并（#56 合并区间）
虽然不是标准归并，但分治思想相通。将区间集不断二分，最后合并左右已排序区间集：
python复制def merge(intervals):
if not intervals:
return []
# 按起点排序
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for curr in intervals[1:]:
last = res[-1]
if curr[0] <= last[1]: # 有重叠
last[1] = max(last[1], curr[1])
else:
res.append(curr)
return res
3.3 多路归并（#23 合并K个升序链表）
将二分归并扩展为多分，有两种优化策略：
- 顺序合并：两两合并，时间复杂度O(kn)
- 堆优化：使用最小堆维护当前各链表头节点，O(nlogk)
python复制def mergeKLists(lists):
import heapq
dummy = ListNode(0)
p = dummy
heap = []
# 初始化堆
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
# 多路归并
while heap:
val, idx, node = heapq.heappop(heap)
p.next = node
p = p.next
if node.next:
heapq.heappush(heap, (node.next.val, idx, node.next))
return dummy.next
4. 性能优化与工程实践
4.1 递归深度优化
当处理大规模数据时，递归可能导致栈溢出。可改为迭代实现，自底向上合并：
- 将每个元素视为已排序的子数组
- 两两合并相邻子数组
- 重复直到只剩一个数组
python复制def mergeSort_iterative(nums):
size = 1
while size < len(nums):
for i in range(0, len(nums), 2*size):
left = nums[i:i+size]
right = nums[i+size:i+2*size]
nums[i:i+2*size] = merge(left, right)
size *= 2
return nums
4.2 混合排序策略
当子数组较小时（如长度<15），切换为插入排序可减少递归开销。实测在力扣平台能提升约20%运行速度：
python复制def hybridSort(nums, threshold=15):
if len(nums) <= threshold:
# 插入排序
for i in range(1, len(nums)):
key = nums[i]
j = i-1
while j >=0 and key < nums[j]:
nums[j+1] = nums[j]
j -= 1
nums[j+1] = key
return nums
mid = len(nums) // 2
left = hybridSort(nums[:mid], threshold)
right = hybridSort(nums[mid:], threshold)
return merge(left, right)
4.3 内存优化技巧
对于C++等语言，可预先分配一个全局临时数组，避免每次合并时重复申请内存。Python中可用切片优化：
python复制temp = [0] * len(nums) # 全局临时数组
def mergeSort_optimized(nums, l, r):
if l >= r:
return
mid = (l + r) // 2
mergeSort_optimized(nums, l, mid)
mergeSort_optimized(nums, mid+1, r)
# 使用预分配空间
i, j, k = l, mid+1, l
while i <= mid and j <= r:
if nums[i] <= nums[j]:
temp[k] = nums[i]
i += 1
else:
temp[k] = nums[j]
j += 1
k += 1
while i <= mid:
temp[k] = nums[i]
i += 1
k += 1
while j <= r:
temp[k] = nums[j]
j += 1
k += 1
nums[l:r+1] = temp[l:r+1]
5. 常见错误与调试技巧
5.1 死循环问题
在链表排序中，如果未正确断链会导致无限递归。建议在分治前打印链表状态验证：
python复制def printList(head):
while head:
print(head.val, end=" -> ")
head = head.next
print("None")
5.2 边界条件处理
合并阶段要特别注意：
- 左子数组耗尽时直接复制右子数组剩余元素
- 右子数组耗尽时直接复制左子数组剩余元素
- 空数组输入情况
5.3 稳定性测试
验证算法是否保持稳定性（相等元素的原始顺序）：
python复制# 测试用例
data = [(2,'a'), (1,'b'), (2,'c'), (3,'d'), (1,'e')]
# 排序后应保持(2,'a')在(2,'c')之前
5.4 性能分析工具
使用Python的cProfile模块定位热点：
python复制import cProfile
cProfile.run('mergeSort(list(range(10000,0,-1)))')
对于链表问题，可可视化节点关系：
python复制def drawList(head):
import graphviz
dot = graphviz.Digraph()
while head and head.next:
dot.node(str(id(head)), str(head.val))
dot.node(str(id(head.next)), str(head.next.val))
dot.edge(str(id(head)), str(id(head.next)))
head = head.next
dot.render('list', view=True)