本文详解如何在Python中正确实现《算法导论》（CLRS）描述的归并排序，重点解决因混淆一维数组索引约定导致的IndexError、越界访问及排序失效问题，并提供可直接运行的修正代码。
本文详解如何在python中正确实现《算法导论》（clrs）描述的归并排序，重点解决因混淆一维数组索引约定导致的`indexerror`、越界访问及排序失效问题，并提供可直接运行的修正代码。
《算法导论》（CLRS）第三版第31页给出的归并排序伪代码基于一维、一索引（1-based）数组模型，而Python列表天然采用零索引（0-based）。若直接逐行翻译伪代码而不调整索引逻辑，极易引发IndexError: list index out of range——典型表现包括访问a[-1]（误将p+i-1用于p=0）、遗漏末尾元素（range(p, r)未覆盖r），或哨兵插入位置错误。
以下为关键问题分析与修正方案：
让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限
? 核心错误定位
merge()中左子数组复制越界
原代码：L[i] = a[p + i - 1]
当p = 0, i = 0→a[-1]（取最后一个元素，非首元素）❌
✅ 正确：L[i] = a[p + i]（零基下，p即起始位置）右子数组起始偏移错误
原代码：R[j] = a[q + j]
CLRS中q是左子数组末尾索引，故右子数组应从q+1开始 → ✅a[q + 1 + j]合并循环范围缺失右边界
原代码：for k in range(p, r)→ 覆盖[p, r-1]，遗漏索引r❌
✅ 正确：for k in range(p, r + 1)→ 覆盖[p, r]初始调用参数错误
原调用：mergesort(X, 0, 10)→r=10超出列表最大索引9❌
✅ 正确：mergesort(X, 0, len(X)-1)
✅ 修正后的完整可运行代码
import math
import numpy as np
X = np.random.randint(0, 10, 10).tolist()
print("Before:", X)
def merge(a, p, q, r):
# 计算左右子数组长度（零基下仍沿用CLRS公式）
n1 = q - p + 1
n2 = r - q
# 初始化临时数组（无需+1空间，哨兵后加）
L = [0] * n1
R = [0] * n2
# 复制：左子数组 a[p..q] → L[0..n1-1]
for i in range(n1):
L[i] = a[p + i] # ✅ 关键修正：去掉 -1
# 复制：右子数组 a[q+1..r] → R[0..n2-1]
for j in range(n2):
R[j] = a[q + 1 + j] # ✅ 关键修正：起始为 q+1
# 添加无穷大哨兵（避免边界检查）
L.append(math.inf)
R.append(math.inf)
i = j = 0
# 合并回原数组 a[p..r]（含端点 r）
for k in range(p, r + 1): # ✅ 关键修正：r+1 确保覆盖
if L[i] <= R[j]:
a[k] = L[i]
i += 1
else:
a[k] = R[j]
j += 1
def mergesort(a, p, r):
if p < r:
q = (p + r) // 2
mergesort(a, p, q) # 左半区：[p, q]
mergesort(a, q + 1, r) # 右半区：[q+1, r]
merge(a, p, q, r) # 合并 [p, q] 和 [q+1, r]
# ✅ 正确调用：末索引为 len-1
mergesort(X, 0, len(X) - 1)
print("After: ", X)⚠️ 注意事项与最佳实践
-
哨兵值选择：
math.inf在数值比较中安全，但若处理非数字类型（如字符串），需改用float('inf')或自定义极大值。 -
空间优化：当前实现每次
merge新建临时数组，时间复杂度仍为 $O(n\log n)$，但额外空间为 $O(n)$；可预分配全局辅助数组以减少内存分配开销。 - 稳定性验证：归并排序天然稳定（相等元素相对顺序不变），本实现保持该特性。
-
调试技巧：在
merge函数开头添加print(f"merge({p},{q},{r}): {a[p:r+1]}")可直观跟踪每轮合并区间。
通过严格对齐Python零索引语义重写CLRS伪代码，不仅能消除运行时错误，更能加深对分治策略与边界条件设计的理解——这是算法工程化落地的关键一步。
