学习笔记 数据结构与算法

归并排序（Merge Sort）

分治思想的经典应用

所属专题： 数据结构与算法基础

核心思想： 分而治之（Divide and Conquer）——递归分解 + 有序合并

时间复杂度： O(n log n)（最坏、平均、最优均一致）

空间复杂度： O(n)（辅助数组）

稳定性： 稳定排序

关键词： 归并排序、分治算法、递归、逆序对、外部排序、主定理

一、算法概述

归并排序（Merge Sort）是计算机科学中最早被提出的排序算法之一，由约翰-冯-诺伊曼（John von Neumann）于1945年在其著名的EDVAC计算机报告中首次描述。归并排序是分治算法（Divide and Conquer）最典型的代表之一，它的核心思想极其简洁却威力强大：将一个大问题分解为若干小问题，分别解决后将结果合并。

在排序领域中，归并排序拥有几个非常引人注目的特性：

指标 数值 说明
最优时间复杂度 O(n log n) 无论数据分布如何，均稳定在此复杂度
平均时间复杂度 O(n log n) 概率意义上的期望时间复杂度
最坏时间复杂度 O(n log n) 不存在快速排序的退化问题
空间复杂度 O(n) 需要与原数组等大的辅助数组
稳定性 稳定 相等元素的相对顺序保持
是否原地排序 否 需要额外 O(n) 空间

归并排序的核心特点

  • 性能稳定： 无论输入数据如何分布，时间复杂度始终为 O(n log n)，这是归并排序最大的优势之一。
  • 空间换时间： O(n) 的额外空间是其最大的代价，但在很多场景下是可以接受的折中。
  • 分治典范： 归并排序完美诠释了分治算法的三个步骤——分解（Divide）、解决（Conquer）、合并（Combine）。

二、核心思想：分而治之

归并排序的核心思想可以用"分而治之"四个字来概括。它将排序一个大数组的问题拆解为两个核心操作：

  1. 分解（Divide）： 将待排序数组从中间位置一分为二，递归地对左右两个子数组进行排序。
  2. 解决（Conquer）： 当子数组的长度为 1 时，它天然是有序的（单个元素的数组不需要排序），递归终止。
  3. 合并（Combine）： 将两个已经有序的子数组合并为一个有序的大数组。这是归并排序的核心操作。

合并操作详解（Merge）

合并两个有序数组的操作是归并排序的核心。假设我们有两个已经排好序的数组 A 和 B，合并的步骤如下：

  1. 创建一个大数组 C，大小为 |A| + |B|。
  2. 使用三个指针 i、j、k 分别指向 A、B、C 的起始位置。
  3. 比较 A[i] 和 B[j]，将较小的元素放入 C[k]，然后移动相应的指针（i 或 j）和 k。
  4. 当其中一个数组的元素全部取完后，将另一个数组剩余的所有元素依次放入 C。

合并过程的时间复杂度为 O(n)，其中 n 是两个子数组的长度之和。合并过程只需要一次遍历，且每个元素只被比较和移动一次。

"合久必分，分久必合。"——归并排序的精髓就在于先无脑地拆分到最简，再精心地合并成有序。

从更高的视角来看，归并排序的过程可以用一棵递归树来描述。树的每一层对应一次分解或合并操作。在分解阶段，数组被逐层二分，直到每个叶子节点只包含一个元素；在合并阶段，叶子节点逐层合并，直到根节点得到完整的有序数组。

归并排序的递归树结构

  • 树的高度（递归深度）：log2n
  • 第 i 层的子数组数量：2i
  • 第 i 层每个子数组的长度：n / 2i
  • 第 i 层合并的总工作量：n（每个元素恰好被处理一次）
  • 所有层合并的总工作量：n × log n

三、自顶向下归并排序（递归实现）

自顶向下（Top-Down）的归并排序是最直观的实现方式。它直接对应分治算法的三个步骤：递归地将数组分成两半，分别排序，然后合并。这是最符合"分治法"思维模式的实现版本，也是教学中最常用的展示方式。

3.1 核心实现（Python）

Python 自顶向下归并排序 
def merge_sort(arr):
    """归并排序（自顶向下递归实现）"""
    if len(arr) <= 1:
        return arr

    # 1. 分解：找到中间位置，一分为二
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # 2. 解决：递归地对左右两半进行排序
    left = merge_sort(left)
    right = merge_sort(right)

    # 3. 合并：将两个有序数组合并为一个
    return merge(left, right)


def merge(left, right):
    """合并两个有序数组"""
    result = []
    i = j = 0

    # 比较两个数组的头部元素，取较小的放入结果
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 将剩余元素全部加入结果
    result.extend(left[i:])
    result.extend(right[j:])

    return result

3.2 原地合并版本（优化空间使用）

上面的实现每次递归都创建新的列表，会产生大量的内存分配和复制开销。更高效的做法是使用一个全局辅助数组，在原数组上进行原地合并操作。

Python 原地合并版本（使用辅助数组） 
def merge_sort_inplace(arr):
    """归并排序（原地修改版）"""
    n = len(arr)
    # 预分配辅助数组，避免反复创建
    temp = [0] * n
    _merge_sort(arr, 0, n - 1, temp)
    return arr


def _merge_sort(arr, left, right, temp):
    """递归函数：对 arr[left..right] 进行排序"""
    if left >= right:
        return

    # 分解
    mid = left + (right - left) // 2

    # 解决
    _merge_sort(arr, left, mid, temp)
    _merge_sort(arr, mid + 1, right, temp)

    # 合并
    _merge(arr, left, mid, right, temp)


def _merge(arr, left, mid, right, temp):
    """合并 arr[left..mid] 和 arr[mid+1..right]"""
    # 复制到辅助数组
    for i in range(left, right + 1):
        temp[i] = arr[i]

    i = left      # 左半部分起始索引
    j = mid + 1   # 右半部分起始索引
    k = left      # 原数组合并位置索引

    while i <= mid and j <= right:
        if temp[i] <= temp[j]:
            arr[k] = temp[i]
            i += 1
        else:
            arr[k] = temp[j]
            j += 1
        k += 1

    # 处理左半部分剩余元素（右半部分剩余元素已在原位）
    while i <= mid:
        arr[k] = temp[i]
        i += 1
        k += 1

3.3 算法执行过程示例

以数组 [38, 27, 43, 3, 9, 82, 10] 为例，自顶向下归并排序的执行过程如下：

执行过程 分解与合并全过程 
初始数组: [38, 27, 43, 3, 9, 82, 10]

=== 分解阶段 ===
第1层分解: [38, 27, 43, 3]  |  [9, 82, 10]
第2层分解: [38, 27] | [43, 3]  |  [9, 82] | [10]
第3层分解: [38] | [27]  |  [43] | [3]  |  [9] | [82]  |  [10]

=== 合并阶段 ===
第3层合并: [27, 38]  |  [3, 43]  |  [9, 82]  |  [10]
第2层合并: [3, 27, 38, 43]  |  [9, 10, 82]
第1层合并: [3, 9, 10, 27, 38, 43, 82]

最终有序数组: [3, 9, 10, 27, 38, 43, 82]

自顶向下归并排序的关键点

  • 递归深度为 O(log n)，对于 n=106 的数据，递归深度仅为约 20 层，不存在栈溢出的风险。
  • 合并操作是归并排序的核心性能瓶颈，优化合并过程的效率可以显著提升整体性能。
  • 辅助数组的预分配（而非递归中频繁创建）可以大幅减少内存分配开销和GC压力。

四、自底向上归并排序（迭代实现）

自底向上（Bottom-Up）的归并排序是另一种实现策略。与自顶向下不同，它不使用递归，而是直接将数组视为若干个长度为 1 的有序子数组，然后通过迭代逐步增大归并的长度，直到整个数组有序。

自底向上的实现方式避免了递归调用的开销，同时消除了递归深度带来的栈空间消耗，在某些场景下性能更优。此外，对于不支持递归或递归开销较大的环境（如某些嵌入式系统），自底向上是唯一可行的实现方式。

4.1 核心实现

Python 自底向上归并排序（迭代实现） 
def merge_sort_bottom_up(arr):
    """归并排序（自底向上迭代实现）"""
    n = len(arr)
    temp = [0] * n
    size = 1  # 子数组大小，从 1 开始倍增长

    while size < n:
        # 遍历数组，对相邻的两个子数组进行合并
        for left in range(0, n - size, size * 2):
            mid = left + size - 1
            right = min(left + size * 2 - 1, n - 1)
            _merge(arr, left, mid, right, temp)
        size *= 2  # 子数组大小倍增

    return arr


def _merge(arr, left, mid, right, temp):
    """合并 arr[left..mid] 和 arr[mid+1..right]"""
    for i in range(left, right + 1):
        temp[i] = arr[i]

    i = left
    j = mid + 1
    k = left

    while i <= mid and j <= right:
        if temp[i] <= temp[j]:
            arr[k] = temp[i]
            i += 1
        else:
            arr[k] = temp[j]
            j += 1
        k += 1

    while i <= mid:
        arr[k] = temp[i]
        i += 1
        k += 1

4.2 自底向上执行过程示例

对于数组 [38, 27, 43, 3, 9, 82, 10]，自底向上归并排序的执行过程：

执行过程 自底向上归并全过程 
初始数组: [38, 27, 43, 3, 9, 82, 10]

size=1: 合并相邻的长度为1的子数组
 合并 [38]和[27] => [27, 38]
 合并 [43]和[3]  => [3, 43]
 合并 [9]和[82]  => [9, 82]
 合并 [10]单独   => [10]
结果: [27, 38, 3, 43, 9, 82, 10]

size=2: 合并相邻的长度为2的子数组
 合并 [27,38]和[3,43] => [3, 27, 38, 43]
 合并 [9,82]和[10]    => [9, 10, 82]
结果: [3, 27, 38, 43, 9, 10, 82]

size=4: 合并相邻的长度为4的子数组
 合并 [3,27,38,43]和[9,10,82] => [3, 9, 10, 27, 38, 43, 82]
结果: [3, 9, 10, 27, 38, 43, 82]

4.3 两种实现方式的对比

对比维度 自顶向下（递归） 自底向上（迭代）
编程复杂度 低，代码简洁直观 中等，边界处理稍复杂
递归/栈开销 有递归调用和栈空间开销 无递归，完全避免栈问题
空间复杂度 O(n + log n)（辅助数组 + 递归栈） O(n)（仅辅助数组）
缓存友好性 较差（跳跃访问模式） 较好（顺序归并）
链表排序 较易实现 较易实现（不需要额外空间）
并行化 天然适合并行 需要额外设计

选择建议

在实际工程中，自顶向下实现更常用于教学和通用场景（代码简洁性优先），而自底向上实现则在性能敏感型场景和对递归深度有限制的环境中更受青睐。对于大规模数据的排序，自底向上的迭代实现往往具有更好的常数因子性能。

五、归并排序的优化技巧

虽然基础的归并排序已经具有 O(n log n) 的稳定性能，但通过一系列优化手段，我们可以进一步提升其实际运行效率。以下是最常用的几种优化策略。

5.1 小数组使用插入排序

当子数组规模较小时（通常阈值设为 7-15 个元素），插入排序的实际运行速度反而快于归并排序。这是因为插入排序在小规模数据上没有递归开销，且利用了 CPU 缓存的局部性原理。这一优化技巧被称为混合排序（Hybrid Sort），也是 TimSort（Python 和 Java 标准库使用的排序算法）的核心思想之一。

Python 小数组优化：插入排序 + 归并排序混合 
INSERTION_THRESHOLD = 10  # 小数组阈值


def merge_sort_optimized(arr):
    """优化后的归并排序——小数组使用插入排序"""
    n = len(arr)
    temp = [0] * n
    _merge_sort_opt(arr, 0, n - 1, temp)
    return arr


def _merge_sort_opt(arr, left, right, temp):
    """递归函数：小数组使用插入排序"""
    # 小数组使用插入排序
    if right - left + 1 <= INSERTION_THRESHOLD:
        insertion_sort(arr, left, right)
        return

    mid = left + (right - left) // 2
    _merge_sort_opt(arr, left, mid, temp)
    _merge_sort_opt(arr, mid + 1, right, temp)

    # 如果数组已经有序，跳过合并
    if arr[mid] <= arr[mid + 1]:
        return

    _merge(arr, left, mid, right, temp)


def insertion_sort(arr, left, right):
    """对 arr[left..right] 进行插入排序"""
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

5.2 避免重复分配辅助数组

基础实现中，每次 merge 调用都创建新的列表（或数组），这会导致大量的内存分配和垃圾回收开销。优化的方式是在递归开始前一次性预分配一个与原数组等大的辅助数组，并在整个排序过程中复用同一个数组。

Python 避免重复分配：预分配辅助数组 
def merge_sort_no_alloc(arr):
    """预分配辅助数组版本，避免重复分配"""
    n = len(arr)
    temp = [0] * n
    _merge_sort_no_alloc(arr, 0, n - 1, temp)
    return arr


def _merge_sort_no_alloc(arr, left, right, temp):
    if left >= right:
        return
    mid = left + (right - left) // 2
    _merge_sort_no_alloc(arr, left, mid, temp)
    _merge_sort_no_alloc(arr, mid + 1, right, temp)

    # 只有当需要合并时才复制
    if arr[mid] > arr[mid + 1]:
        for i in range(left, right + 1):
            temp[i] = arr[i]

        i, j, k = left, mid + 1, left
        while i <= mid and j <= right:
            if temp[i] <= temp[j]:
                arr[k] = temp[i]
                i += 1
            else:
                arr[k] = temp[j]
                j += 1
            k += 1
        while i <= mid:
            arr[k] = temp[i]
            i += 1
            k += 1

5.3 检测是否已经有序

在合并前检查 arr[mid] <= arr[mid+1]：如果左右两半的最大值已经小于等于右半的最小值，说明两个子数组已经整体有序，可以跳过合并步骤。这在处理近乎有序的数据时能带来显著的性能提升。

5.4 优化总结

归并排序优化清单

  1. 小数组用插入排序： 规模小于阈值时切换到插入排序（通常阈值 = 7 ~ 15）。
  2. 预分配辅助数组： 在顶层一次性创建辅助数组，贯穿整个排序过程。
  3. 跳过有序数组的合并： 合并前检查 arr[mid] <= arr[mid+1]，是则跳过。
  4. 消除对右半部分的回写： 合并时如果右半部分先耗尽，左半部分剩余元素已在原位，无需复制。
  5. 内存优化： 归并时交替使用原数组和辅助数组作为目标数组，减少数据复制次数。

六、归并排序的稳定性分析

排序算法的稳定性（Stability）是指：如果待排序序列中存在值相等的元素，经过排序后，这些相等元素的相对顺序保持不变。

归并排序是稳定排序。这一性质源自合并操作中的关键决策：当两个子数组中存在相等元素时，我们优先取左侧子数组的元素。具体来说，在 _merge 函数的比较语句中，使用 temp[i] <= temp[j]（而不是 <）保证了当左右两边的元素相等时，来自左侧子数组（原来就在前面）的元素被先放入结果中。

Python 稳定性关键：等号的处理 
# 稳定版本：使用 <=，相等时优先取左侧元素
if temp[i] <= temp[j]:
    arr[k] = temp[i]   # 左侧元素保持在前
    i += 1

# 不稳定版本：使用 <，相等时取右侧元素（破坏了稳定性）
if temp[i] < temp[j]:
    arr[k] = temp[i]
    i += 1

稳定性的实际意义

在对多个字段进行排序时，稳定性非常重要。例如，先按"成绩"排序，再按"班级"排序——如果排序算法是稳定的，那么第二次排序后，同一班级内的学生将依然保持按成绩排序的顺序。归并排序的稳定性使其特别适合此类多关键字排序场景。

七、归并排序的典型应用

归并排序的独特性质使其在以下场景中得到广泛应用。

7.1 外部排序（External Sorting）

当待排序数据量远超计算机内存容量时，传统的内部排序算法（如快速排序）无法工作，因为数据无法一次性载入内存。此时，归并排序的思想被用于外部排序——这是归并排序最重要的工程应用之一。

外部排序的两阶段流程

  1. 第一阶段： 将大文件分割为多个可以载入内存的块，对每个块使用快速排序等内部排序算法进行排序，将排序后的块写回磁盘（这些有序块称为"顺串"或 Run）。
  2. 第二阶段： 使用多路归并（K-Way Merge）的方式，一次性从 K 个顺串中读取最前面的元素，比较后输出最小的元素，重复此过程直到所有顺串合并完成。
Python 多路归并（K-Way Merge）模拟 
import heapq


def k_way_merge(sorted_arrays):
    """
    多路归并：将 K 个有序数组合并为一个有序数组
    使用最小堆（优先队列）来提高效率
    """
    result = []
    # 最小堆，存储 (值, 数组索引, 元素索引)
    heap = []

    # 初始化堆：将每个数组的第一个元素入堆
    for i, arr in enumerate(sorted_arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))

    # 不断取堆顶最小元素，并从相应数组中补充下一个元素
    while heap:
        val, arr_idx, elem_idx = heapq.heappop(heap)
        result.append(val)

        # 如果该数组还有下一个元素，入堆
        if elem_idx + 1 < len(sorted_arrays[arr_idx]):
            next_val = sorted_arrays[arr_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))

    return result


# 示例：5个有序数组的多路归并
arrays = [
    [3, 7, 15],
    [1, 8, 20],
    [5, 12, 18],
    [2, 10, 22],
    [6, 9, 11]
]

result = k_way_merge(arrays)
print(result)  # [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 18, 20, 22]

7.2 链表排序

由于链表的随机访问效率极低（O(n) 时间才能找到中间节点），快速排序和堆排序在链表上表现不佳。而归并排序只需要顺序访问数据，天然适合链表的物理结构。使用归并排序对链表排序，甚至可以实现 O(1) 的额外空间复杂度。

Python 单向链表的归并排序 
class ListNode:
    """单向链表节点"""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def merge_sort_linked_list(head):
    """对单向链表进行归并排序，空间复杂度 O(1)"""
    if not head or not head.next:
        return head

    # 1. 快慢指针找到链表的中点
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 2. 分割链表
    right_head = slow.next
    slow.next = None

    # 3. 递归排序左右两部分
    left = merge_sort_linked_list(head)
    right = merge_sort_linked_list(right_head)

    # 4. 合并两个有序链表
    return merge_two_lists(left, right)


def merge_two_lists(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

7.3 求逆序对（Inversion Count）

逆序对是衡量数组有序程度的重要指标。在一个数组中，如果 i < j 但 a[i] > a[j]，则 (i, j) 构成一个逆序对。求逆序对的经典解法就是利用归并排序的合并过程——在合并阶段，每当从右半部分取一个元素时，左半部分剩余的所有元素都与该元素构成逆序对。

Python 利用归并排序求逆序对数量 
def count_inversions(arr):
    """利用归并排序计算数组中的逆序对数量"""
    n = len(arr)
    temp = [0] * n
    return _count_inversions(arr, 0, n - 1, temp)


def _count_inversions(arr, left, right, temp):
    """返回 arr[left..right] 中的逆序对数量"""
    if left >= right:
        return 0

    mid = left + (right - left) // 2
    count = 0

    # 左半部分的逆序对 + 右半部分的逆序对
    count += _count_inversions(arr, left, mid, temp)
    count += _count_inversions(arr, mid + 1, right, temp)

    # 跨左右两半的逆序对
    count += _merge_and_count(arr, left, mid, right, temp)

    return count


def _merge_and_count(arr, left, mid, right, temp):
    """合并并统计跨两半的逆序对"""
    for i in range(left, right + 1):
        temp[i] = arr[i]

    i, j, k = left, mid + 1, left
    count = 0

    while i <= mid and j <= right:
        if temp[i] <= temp[j]:
            arr[k] = temp[i]
            i += 1
        else:
            # 关键：temp[j] < temp[i]，且 i < j
            # 左半部分从 i 到 mid 的所有元素都大于 temp[j]
            count += (mid - i + 1)
            arr[k] = temp[j]
            j += 1
        k += 1

    while i <= mid:
        arr[k] = temp[i]
        i += 1
        k += 1

    return count


# 示例
arr = [2, 4, 1, 3, 5]
print(count_inversions(arr))  # 输出: 3
# 逆序对：(2,1), (4,1), (4,3)

利用归并排序求逆序对的时间复杂度为 O(n log n)，而暴力枚举法的时间复杂度为 O(n2)。对于 n=105 的数据规模，归并排序方法只需不到 0.1 秒，而暴力枚举需要数小时。

7.4 TimSort——Python 和 Java 的标准排序算法

值得一提的是，Python 的 list.sort() 和 Java 的 Arrays.sort(Object[]) 所使用的排序算法 TimSort，其本质是归并排序的变体。TimSort 巧妙地结合了归并排序和插入排序，并利用了数据中已有的"自然有序"（Natural Run）序列，在真实数据上的性能极为出色。

工程应用一览

应用场景 使用归并排序的原因 典型代表
数据库外部排序 顺序访问磁盘，分治处理大文件 PostgreSQL、MySQL
链表排序 不需要随机访问，空间效率高 各语言标准库链表排序
通用高性能排序 稳定性 + O(n log n) 保证 TimSort（Python/Java）
逆序对统计 合并过程中的自然计数 算法竞赛、数据分析
并行排序 分治结构天然可并行 多线程归并排序

八、时间复杂度分析与主定理推导

8.1 递归关系式

归并排序的时间复杂度可以用递归关系式来精确描述。设 T(n) 表示对 n 个元素进行归并排序所需的时间，则有：

T(n) = 2 · T(n/2) + O(n)

其中：

8.2 主定理推导

上述递推关系式符合主定理（Master Theorem）的标准形式。主定理描述了形如 T(n) = aT(n/b) + f(n) 的递推关系式的渐近复杂度。

主定理（Master Theorem）

对于递推式 T(n) = aT(n/b) + f(n)，其中 a >= 1, b > 1，f(n) 是渐近正函数：

  1. 如果 f(n) = O(nlogba - ε) 对某个 ε > 0 成立，则 T(n) = Θ(nlogba)
  2. 如果 f(n) = Θ(nlogba)，则 T(n) = Θ(nlogba log n)
  3. 如果 f(n) = Ω(nlogba + ε) 对某个 ε > 0 成立，且 af(n/b) <= cf(n) 对某个 c < 1 和足够大的 n 成立，则 T(n) = Θ(f(n))

代入归并排序的参数：

这符合主定理的情况2，因此：

T(n) = Θ(nlogba log n) = Θ(n log n)

8.3 递推展开验证

不使用主定理，我们也可以通过递推展开来验证 O(n log n) 的结果：

数学推导 递推展开过程 
T(n) = 2T(n/2) + cn                                           [第1层]
     = 2[2T(n/4) + c(n/2)] + cn = 4T(n/4) + 2cn             [第2层]
     = 4[2T(n/8) + c(n/4)] + 2cn = 8T(n/8) + 3cn             [第3层]
     = ...
     = 2^k T(n/2^k) + kcn                                    [第k层]

当 n/2^k = 1 时，即 k = log₂n 时递归终止：
     T(n) = nT(1) + cn log₂n
          = O(n) + O(n log n)
          = O(n log n)

8.4 空间复杂度分析

归并排序的空间复杂度由两部分构成：

因此，总空间复杂度为 O(n + log n) = O(n)。对于自底向上的实现，由于不使用递归，空间复杂度可以降低到 O(n)（仅辅助数组）。

关于"原地归并排序"的说明

虽然理论上存在原地归并排序（In-Place Merge Sort）算法（如 Kronrod 算法），但其实现极其复杂且常数因子巨大，实际运行速度反而比标准的 O(n) 空间版本慢得多。因此，在工程实践中，O(n) 空间版本的归并排序仍然是唯一的实用选择。这也是"没有免费的午餐"在算法设计中的一个经典体现。

九、各主流语言实现示例

归并排序在不同编程语言中的实现风格各具特色。以下是几个主流语言的实现示例。

9.1 C 语言实现

C 归并排序 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left, j = mid + 1, k = left;

    // 复制到临时数组
    memcpy(temp + left, arr + left, (right - left + 1) * sizeof(int));

    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j])
            arr[k++] = temp[i++];
        else
            arr[k++] = temp[j++];
    }

    while (i <= mid)
        arr[k++] = temp[i++];
}

void merge_sort(int arr[], int left, int right, int temp[]) {
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;
    merge_sort(arr, left, mid, temp);
    merge_sort(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

void sort(int arr[], int n) {
    int *temp = (int *)malloc(n * sizeof(int));
    merge_sort(arr, 0, n - 1, temp);
    free(temp);
}

9.2 Java 实现

Java 归并排序（泛型版本） 
public class MergeSort {

    public static <T extends Comparable<? super T>> void sort(T[] arr) {
        T[] temp = (T[]) new Comparable[arr.length];
        sort(arr, 0, arr.length - 1, temp);
    }

    private static <T extends Comparable<? super T>> void
            sort(T[] arr, int left, int right, T[] temp) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        sort(arr, left, mid, temp);
        sort(arr, mid + 1, right, temp);

        // 如果已有序，跳过合并
        if (arr[mid].compareTo(arr[mid + 1]) <= 0)
            return;

        merge(arr, left, mid, right, temp);
    }

    private static <T extends Comparable<? super T>> void
            merge(T[] arr, int left, int mid, int right, T[] temp) {
        System.arraycopy(arr, left, temp, left, right - left + 1);

        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (temp[i].compareTo(temp[j]) <= 0)
                arr[k++] = temp[i++];
            else
                arr[k++] = temp[j++];
        }
        while (i <= mid)
            arr[k++] = temp[i++];
    }
}

9.3 Go 语言实现

Go 归并排序 
package main

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

9.4 JavaScript 实现

JavaScript 归并排序 
function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

9.5 Rust 实现

Rust 归并排序（泛型 + 原地版本） 
pub fn merge_sort<T: Ord + Copy>(arr: &mut [T]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }

    let mut temp = vec![arr[0]; n]; // 预分配辅助数组
    merge_sort_inner(arr, 0, n - 1, &mut temp);
}

fn merge_sort_inner<T: Ord + Copy>(
    arr: &mut [T], left: usize, right: usize, temp: &mut [T],
) {
    if left >= right {
        return;
    }

    let mid = left + (right - left) / 2;
    merge_sort_inner(arr, left, mid, temp);
    merge_sort_inner(arr, mid + 1, right, temp);

    // 如果已经有序，跳过合并
    if arr[mid] <= arr[mid + 1] {
        return;
    }

    // 复制到辅助数组
    for i in left..=right {
        temp[i] = arr[i];
    }

    let (mut i, mut j, mut k) = (left, mid + 1, left);
    while i <= mid && j <= right {
        if temp[i] <= temp[j] {
            arr[k] = temp[i];
            i += 1;
        } else {
            arr[k] = temp[j];
            j += 1;
        }
        k += 1;
    }

    while i <= mid {
        arr[k] = temp[i];
        i += 1;
        k += 1;
    }
}

十、核心要点总结

十一、进一步思考

延伸学习与练习

  1. 手写实现： 尝试在不看参考代码的情况下，手写归并排序的自顶向下和自底向上两种实现。
  2. 性能对比： 编写测试程序比较归并排序、快速排序、堆排序在处理不同数据分布（随机、有序、逆序、大量重复）时的性能差异。
  3. 并行归并排序： 学习 Fork/Join 框架（Java）或 multiprocessing 库（Python），实现并行化的归并排序。
  4. 多路归并： 尝试实现 K 路归并排序（将数组分为 K 个子数组而不是 2 个），分析其性能特征。
  5. TimSort 源码阅读： 阅读 Python (listsort.c) 或 Java (TimSort.java) 中 TimSort 的源码，理解其对归并排序的工程优化。
  6. 主定理练习： 尝试用主定理分析其他分治算法的时间复杂度（如 Strassen 矩阵乘法、大整数乘法 Karatsuba 算法等）。

面试高频问题

  • 归并排序和快速排序的异同点是什么？各自适用于什么场景？
  • 如何实现链表的归并排序？时间复杂度是多少？
  • 归并排序的空间复杂度为什么是 O(n)？是否可以优化到 O(1)？
  • 如何利用归并排序的思想求数组中的逆序对数量？
  • 描述外部排序的原理，归并排序在其中的作用是什么？
  • 自顶向下和自底向上归并排序有什么区别？各自的优缺点是什么？
  • TimSort 相比传统归并排序做了哪些优化？