一文搞懂归并排序进阶：逆序对与链表排序实战

为什么归并排序值得进阶学习

很多同学学会基础排序后，会把归并排序（merge-sort）简单理解为“先拆半、再合并”的排序模板。但在算法面试与高频题中，归并排序真正的价值不只是排序，而是利用分治过程中的有序信息，在线性合并阶段完成额外统计或重组。

典型场景有两个：

• 统计数组中的逆序对数量；
• 在 O(n log n) 时间、O(1) 额外空间内排序链表。

它们表面上一个是计数题，一个是排序题，底层却共享同一个分治框架：递归缩小问题规模，在合并两个有序区间时用双指针处理跨区间关系。

分治模型：问题如何被拆成两半

归并排序的核心流程可以概括为三步：

1. 分解：把当前区间从中间切分；
2. 解决：递归处理左右两个子区间；
3. 合并：将两个已经有序的子区间合并，并处理跨越中点的贡献。

普通排序题中，第三步只负责生成有序数组；逆序对统计中，第三步还要统计“左边值大于右边值”的数对；链表排序中，第三步则是把两个有序链表节点重新连接。

方案对比：暴力枚举为什么不够

以逆序对为例，逆序对的定义是：当 i < j 且 nums[i] > nums[j] 时，(i, j) 构成一个逆序对。

最直接的做法是双重循环枚举所有数对：

def count_inversion_pairs_brutal(nums):
    count = 0
    n = len(nums)
    # 枚举每个左侧元素，再寻找右侧更小元素
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count


print(count_inversion_pairs_brutal([7, 5, 6, 4]))
# 输出：5

这种方法时间复杂度为 O(n²)。当 n 达到 10^5 时，比较次数可能达到百亿量级，无法通过常规时间限制。

归并分治的优势在于：左右内部的逆序对由递归统计，而跨左右两部分的逆序对可以在合并有序数组时一次性计算，总时间复杂度降为 O(n log n)。

实战一：归并排序统计逆序对

核心计数逻辑

假设左半区和右半区已经分别有序。使用双指针 i、j 合并：

• 如果 nums[i] <= nums[j]，当前左侧元素不与 nums[j] 构成逆序对，放入 nums[i]；
• 如果 nums[i] > nums[j]，由于左半区有序，从 i 到左半区末尾的所有元素都大于 nums[j]，因此一次性增加 mid - i + 1 个逆序对。

这一步是整个算法的关键：不要逐个移动左侧指针计数，而要利用左半区的有序性批量统计。

Python 可运行代码

def count_reverse_pairs(nums):
    """统计数组中逆序对数量，返回计数，同时原地排序 nums。"""
    temp = [0] * len(nums)

    def merge_sort(left, right):
        # 递归终止：区间为空或只有一个元素
        if left >= right:
            return 0

        mid = (left + right) // 2

        # 1. 先统计左右内部逆序对
        count = merge_sort(left, mid)
        count += merge_sort(mid + 1, right)

        # 2. 统计跨越中点的逆序对
        i = left
        for j in range(mid + 1, right + 1):
            # 左半区有序，跳过不大于 nums[j] 的元素
            while i <= mid and nums[i] <= nums[j]:
                i += 1
            # 此时 nums[i...mid] 都大于 nums[j]
            count += mid - i + 1

        # 3. 正常归并两个有序区间
        p1, p2 = left, mid + 1
        p = left

        while p1 <= mid and p2 <= right:
            if nums[p1] <= nums[p2]:
                temp[p] = nums[p1]
                p1 += 1
            else:
                temp[p] = nums[p2]
                p2 += 1
            p += 1

        while p1 <= mid:
            temp[p] = nums[p1]
            p1 += 1
            p += 1

        while p2 <= right:
            temp[p] = nums[p2]
            p2 += 1
            p += 1

        # 将归并结果复制回原数组
        for k in range(left, right + 1):
            nums[k] = temp[k]

        return count

    return merge_sort(0, len(nums) - 1)


if __name__ == "__main__":
    data = [7, 5, 6, 4]
    print(count_reverse_pairs(data))  # 5
    print(data)                       # [4, 5, 6, 7]

复杂度分析

• 时间复杂度：每一层归并处理全部 n 个元素，共有 O(log n) 层，因此为 O(n log n)；
• 空间复杂度：递归栈为 O(log n)，临时数组为 O(n)，总体为 O(n)；
• 稳定性：合并时使用 nums[p1] <= nums[p2]，相等元素优先取左侧，可保持稳定性。

实战二：归并思想排序链表

为什么链表适合归并排序

数组归并排序通常需要额外空间保存合并结果，而链表可以通过修改指针完成节点连接，不必按物理位置连续移动元素。因此链表排序可以做到：

• 时间复杂度 O(n log n)；
• 递归栈 O(log n)；
• 不计递归栈时，额外节点空间 O(1)。

先找中点，再切链，最后合并

链表归并最容易出错的地方是“切链”。使用快慢指针找到中点后，必须让左半链表的尾节点指向 None，否则递归处理左半部分时会继续访问到右半节点。

下面代码采用前置虚拟头节点合并有序链表，能减少大量头节点判空逻辑。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def sort_list(head):
    """使用自顶向下的归并排序链表。"""
    # 空链表或只有一个节点时天然有序
    if head is None or head.next is None:
        return head

    # 找到中点：slow 最终停在前半部分尾部
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None  # 关键：切断左右链表

    # 分治排序左右两段
    left = sort_list(head)
    right = sort_list(mid)

    # 合并两个有序链表
    dummy = ListNode(0)
    tail = dummy

    while left and right:
        if left.val <= right.val:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next
        tail = tail.next

    # 剩余节点直接拼接
    tail.next = left if left else right
    return dummy.next


def build_list(values):
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def to_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


if __name__ == "__main__":
    head = build_list([4, 2, 1, 3])
    sorted_head = sort_list(head)
    print(to_list(sorted_head))  # [1, 2, 3, 4]

复杂度分析

• 时间复杂度：每层总共遍历 O(n) 个节点，递归深度 O(log n)，总复杂度 O(n log n)；
• 空间复杂度：只修改指针，不新建数据节点；递归栈为 O(log n)；
• 稳定性：合并阶段相等节点优先接左侧链表，排序稳定。

两种题型背后的统一抽象

数组逆序对和链表排序虽然数据结构不同，但都遵循相同决策框架：

• 能否把问题从中间分成两个规模相近的子问题；
• 子问题解决后，两部分是否具备有序性；
• 能否用双指针在线性时间内处理跨两部分的关系；
• 合并后的结果是否能继续供上层使用。

一旦满足这些条件，归并排序就从一个“排序算法”升级为一种“有序区间信息合并工具”。

避坑总结：高频错误与修正方法

1. 逆序对重复计数或漏计数

常见错误是在递归左右区间后，又对整个区间的所有数对重新扫描，导致左右内部逆序对被重复统计。

修正方法是严格区分三类贡献：左半内部、右半内部、跨越中点。递归只负责前两类，当前合并层只统计第三类。

2. 相等元素被误判为逆序对

题目中的逆序对要求是严格大于，即 nums[i] > nums[j]。如果写成 nums[i] >= nums[j]，在存在重复值时会多算。

修正方法是在跳过左半区元素和归并比较时都使用 <=，例如 while nums[i] <= nums[j]: i += 1。

3. 链表找中点后忘记切断

错误现象是递归无法正常终止，或者排序后链表出现环、重复节点。原因通常是只保存了 mid = slow.next，却没有执行 slow.next = None。

修正方法是切分后立刻断链，确保左链表以 slow 结尾，右链表从 mid 开始。

4. 快慢指针初始值不当导致死循环

两节点链表中，如果快慢指针都从 head 开始，且循环条件是 while fast and fast.next，中点可能落到第二个节点，左半部分无法缩小，从而无限递归。

修正方法是让快指针初始化为 head.next，即 slow, fast = head, head.next，保证两节点时切分位置稳定。

5. 数组成果没有复制回原数组

有些实现把归并结果写入 temp 后直接返回，却没有复制回 nums。上层拿到的左右区间仍然无序，跨区间计数会失效。

修正方法是每一层归并结束后，将 temp[left:right+1] 拷回原数组对应区间，保证递归返回的区间一定有序。

归并排序进阶题的突破口从来不是背模板，而是理解“有序之后，双指针可以批量处理关系”。掌握这一点，逆序对统计、区间计数、链表归并等问题都会回到同一个清晰的分治框架。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。