Coding Interview Prep · 课时

归并排序：分治、排序、合并

Q: 「归并排序：分治、排序、合并」课时是免费的吗？

是的 — 「归并排序：分治、排序、合并」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

Q: 「归并排序：分治、排序、合并」这节课中我会学到什么？

递归实现归并排序，跟踪分治树，并解释它为何在所有情况下都能保证 O(n log n)。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

Q: 「归并排序：分治、排序、合并」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

递归实现归并排序，跟踪分治树，并解释它为何在所有情况下都能保证 O(n log n)。

归并排序：分治、排序、合并 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

分治直觉

归并排序是一种经典的分治算法：将数组分成两半，递归地分别排序，然后 merge 两个有序部分，得到一个有序结果。其关键在于，归并两个有序数组只需要 O(n) 时间，远低于从头开始排序。这种分解会产生一棵具有 log n 层的递归树，每层都需要 O(n) 的归并工作，因此得到比较排序的最优复杂度界限O(n log n)。

# High-level merge sort structure
def merge_sort(arr):
    # Base case: 0 or 1 element already sorted
    if len(arr) <= 1:
        return arr
    # Divide
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])   # sort right half
    # Conquer (merge)
    return merge(left, right)

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

归并步骤详解

归并两个有序数组时，请维护两个指针，每个指针对应一半数组。比较两个数组前端的元素，将较小者 copy 到输出中，并前移对应的指针。当其中一半耗尽后，直接复制另一半的剩余元素。该步骤的时间复杂度为 O(n)，输出数组的空间复杂度为 O(n)。归并步骤是归并排序的算法核心——请务必深入理解。

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= preserves stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]

完整的归并排序实现

将分治与合并结合起来：递归调用不断将问题规模减半，直到只剩下单个元素（显然已经有序），然后由合并调用将它们重新合并。递归树的每一层总共都会合并相同的 n 个元素（这些元素分布在多个合并操作中）。递归深度为 log₂(n)，因此总时间复杂度为 O(n log n)，合并输出数组需要 O(n) 辅助空间，调用栈深度还需要 O(log n) 空间。

def merge_sort_full(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_full(arr[:mid])
    right = merge_sort_full(arr[mid:])
    # Merge the two sorted halves
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: merged.append(left[i]);  i += 1
        else:                   merged.append(right[j]); j += 1
    merged.extend(left[i:] + right[j:])
    return merged

print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]

归并排序递归树

请想象 n=8 时归并排序的递归树：第 0 层有一个包含 8 个元素的数组；第 1 层有两个包含 4 个元素的数组；第 2 层有四个包含 2 个元素的数组；第 3 层有八个单元素数组（基本情况）。向上合并时，第 3→2 层总共合并 8 个元素，第 2→1 层总共合并 8 个元素，第 1→0 层总共合并 8 个元素。这就是 3 层 × 8 个元素 = 24 次操作 ≈ 8 × log₂(8) = 24。这验证了 O(n log n)。

# Trace the tree depth
level_work = []

def merge_sort_traced(arr, depth=0):
    if depth >= len(level_work):
        level_work.append(0)
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_traced(arr[:mid],  depth+1)
    right = merge_sort_traced(arr[mid:],  depth+1)
    level_work[depth] += len(arr)  # track merge work
    merged = sorted(left + right)  # simplified merge
    return merged

merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
    print(f'Level {d}: {work} elements merged')

原地归并排序

标准的递归归并排序会为合并输出分配 O(n) 辅助空间。虽然存在原地归并排序，但它很复杂，而且常数因子很大——在面试中很少被要求实现。面试中更常见的追问是：“您能否在 O(1) 额外空间内完成归并排序？”正确答案是：“理论上可以，但实际实现要么牺牲 O(n) 空间，要么增加复杂度；Python 的 Timsort 在合并时使用 O(n) 空间。”

# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
    n = len(arr)
    width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            left  = arr[i:i+width]
            right = arr[i+width:i+2*width]
            # Merge and put back
            merged = []
            a, b = 0, 0
            while a < len(left) and b < len(right):
                if left[a] <= right[b]: merged.append(left[a]);  a+=1
                else:                   merged.append(right[b]); b+=1
            merged += left[a:] + right[b:]
            arr[i:i+len(merged)] = merged
        width *= 2
    return arr

print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]

归并排序是稳定的

归并排序是稳定的：在合并后的输出中，左半部分的相等元素始终出现在右半部分的相等元素之前。这是通过在优先选择左侧元素时使用 <=（而不是 <）来保证的。稳定性对于多关键字排序很重要。Python 的内置 sorted() 和 list.sort() 使用 Timsort，同样具有稳定性，时间复杂度为 O(n log n)，因此是所有生产代码的安全选择。

# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items)  # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)

合并 K 个有序数组

对于总共包含 n 个元素的 k 个有序数组，可以通过反复合并数组对来完成合并（类似淘汰赛赛程），时间复杂度为 O(n log k)。每个合并层都会处理 n 个元素，共有 log k 层。另一种方法是使用大小为 k 的最小堆：将每个数组中当前剩余的最小元素推入堆中，弹出最小值，再将该元素所属数组的下一个元素推入堆中。堆方法的时间复杂度同样为 O(n log k)，但当 k 非常大时更加节省内存。

import heapq

def merge_k_sorted(arrays):
    result = []
    heap = []
    # Push first element from each array with array index
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    while heap:
        val, arr_i, elem_i = heapq.heappop(heap)
        result.append(val)
        if elem_i + 1 < len(arrays[arr_i]):
            next_val = arrays[arr_i][elem_i + 1]
            heapq.heappush(heap, (next_val, arr_i, elem_i+1))
    return result

arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs))  # [1,2,3,4,5,6,7,8,9]

使用归并排序统计逆序对

要在 O(n log n) 时间内统计逆序对（满足 a[i] > a[j] 且 i < j 的元素对），可以使用修改后的归并排序。在合并步骤中，当右子数组中的元素小于左子数组中的元素时，它会与左子数组中所有剩余的元素构成逆序对。此时将 len(left) - i 加到计数中。

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left,  l_inv = count_inversions(arr[:mid])
    right, r_inv = count_inversions(arr[mid:])
    merged = []
    inversions = l_inv + r_inv
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inversions += len(left) - i  # all remaining left elements > right[j]
    merged.extend(left[i:] + right[j:])
    return merged, inversions

_, inv = count_inversions([3, 1, 2])
print(inv)  # 2: (3,1) and (3,2)

归并排序与快速排序

归并排序在所有情况下都保证 O(n log n)，具有稳定性，并且更适合链表和外部排序。快速排序的平均情况为 O(n log n)，但最坏情况为 O(n²)；它是原地算法，只需 O(log n) 的栈空间，并且由于数组上的缓存效率更高，实际运行时通常更快。Python 的内置 sort 使用 Timsort（一种归并排序变体）——始终是正确的默认选择。

# Head-to-head complexity comparison:
# Algorithm     | Best  | Avg      | Worst  | Space  | Stable
# Bubble sort   | O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Insertion sort| O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Merge sort    | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort    | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort     | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No

print('Merge sort: stable, O(n log n) guaranteed, O(n) space')

外部排序：大规模场景下的归并排序

归并排序是外部排序背后的算法，适用于数据量太大而无法全部装入 RAM 的情况。数据会按块读取，每个数据块在内存中排序，然后从磁盘合并这些数据块。合并步骤每次从每个有序数据段读取一个元素，同时只在内存中保留 O(k) 个元素（每个数据段一个）。这就是归并排序被用于数据库、Hadoop MapReduce 和经典磁带排序算法的原因。

# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
    chunks = []
    for i in range(0, len(data), chunk_size):
        chunk = sorted(data[i:i+chunk_size])  # sort in-memory
        chunks.append(chunk)
    print(f'Created {len(chunks)} sorted chunks')
    # Merge all chunks
    import heapq
    heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
    heapq.heapify(heap)
    result = []
    while heap:
        val, ci, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(chunks[ci]):
            heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
    return result

print(external_sort(list(range(20,0,-1)), 5)[:10])

归并排序总结与面试技巧

在面试中，清晰地实现归并排序可以展示您对递归、合并步骤以及分治法的理解。常见追问包括：

为什么是 O(n log n) 而不是 O(n²)？（log n 层 × 每层 n 的工作量）
它稳定吗？（是的，在合并时使用 <=）
需要多少空间？（O(n) 辅助空间 + O(log n) 栈空间）
可以用迭代方式实现吗？（可以，使用自底向上的归并排序）
如何将它用于链表？（比用于数组更容易——不会产生 O(n) 的切片开销；使用快慢指针找到中点）

# One-shot merge sort for interview clarity:
def ms(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: res.append(l[i]); i+=1
        else:             res.append(r[j]); j+=1
    return res + l[i:] + r[j:]

print(ms([5,2,4,6,1,3]))  # [1,2,3,4,5,6]

快速检查

测试您对本课数据结构与算法——编程面试准备相关概念的理解。

课程回顾

本课中您学到了：归并排序在中点处分割数组，递归地对两半分别排序，再以 O(n) 的时间合并两个有序部分——在 log n 层递归中产生 O(n log n) 的总运行时间；合并步骤使用 <= 在相等时选择左侧元素，从而保证稳定性；以及归并排序是链表、外部排序以及需要稳定性时的首选算法——而当空间有限时，对于内存中的数组则更适合使用快速排序。接下来我们将实现快速排序，并探索枢轴选择策略。

常见问题解答