归并排序详解：从分治原理到多路归并实战，高效合并有序日志文件

先交代一个上周真实发生的场景运维丢给我三份线上日志文件每份内部都按时间戳排得整整齐齐但三份混在一起就是一团乱麻。老板要一条从早到晚的全量时间线总共八十多万行。如果五年前的我肯定直接读进内存一句sorted()梭哈。但现在数据量上来了、内存也吃紧而且数据本身已经以“分段有序”的形式存在——这个结构恰好指向一个被低估太久的算法归并排序。用归并排序的思路来做这台机器连 1GB 内存都不用吃满几十秒就能把三份“局部有序”的文件整理成一份“全局有序”的输出。这篇我就把归并排序按我自己理解的方式彻底整理一遍从分治原理讲到递归和迭代实现再聊工程优化、典型坑位最后用多路归并解决实际的数据整理问题。如果你只是背过“时间复杂度 O(n log n)”这句八股那这篇能帮你补齐边界条件和内存细节如果你正愁怎么把多个有序文件合并成一个可以直接跳到第 6 章抄实战代码。1. 为什么偏偏用归并排序来“整理”1.1 从两堆扑克牌说起有人觉得归并排序难懂是因为名字太拗口。“归并”拆开看就是“归”和“并”归是回归、并是合并。整个算法的动作拆到底只有两个先拆到不能再拆再把拆出来的小块两两合并。合并的时候有一个特别朴素的操作小时候玩扑克牌都干过左右手各捏一叠已经按大小排好的牌每次比较两叠最上面的那张谁小就抽谁放到桌面上。这样重复下去等到两叠牌都抽空桌面上就是一叠完整有序的大牌。这个“抽牌”的动作放到数组里就是一次 merge。归并排序的全过程就是反复执行这个动作把一个数组从中间一切两半左半边排好、右半边排好然后用一次 merge 把它们合并成一个有序整体左右半边又是各自递归地“一切两半、排好、合并”得来的。拆到什么时候为止拆到只剩一个元素或空数组单元素天然有序不需要再排。1.2 归并排序的特殊脾气同样都是排序为什么说归并排序尤其适合“整理类”任务因为它有几个别的算法给不了的特性第一稳定。相等的元素在排序前后相对位置不会变。举例来说按“时间”排序时同一秒内先入库的日志还在前面这对审计类需求几乎是硬指标。而快速排序的普通实现往往是不稳定的要额外费劲才能保持稳定。第二最坏情况也有保障。快速排序在数据已经有序或接近有序时如果基准选得不好会退化到 O(n²)归并排序不管输入长什么样永远是均摊式的 O(n log n)。对于“不知道线上数据会变成什么样”的生产环境这种确定性很珍贵。第三天生支持顺序访问。它不依赖随机读取数组下标做交换主要操作就是按序遍历和合并所以它天然适合处理链表也适合做磁盘上的外部排序——内存装不下全量数据时只能靠归并在小片段之间做吞吐。第四能处理“分段已有序”的数据。这就是我开头那个日志场景的关键三份文件各自有序需要的不再是“无序→有序”的重排而是“多个有序序列→一个有序序列”的归并。堆排序做不到、快排也要整体重来归并排序的 merge 阶段直接就是干这个的。2. 归并排序核心思想全拆解2.1 分治三板斧拆、排、合分治法的套路可以用三个动词概括分解、解决、合并。归并排序里分解就是找到中点mid把区间[left, right)切成[left, mid)和[mid, right)解决就是递归地对两边分别排序合并就是调用 merge 把两个有序子区间拼成一个大的有序区间。这里我刻意用了左闭右开区间后面代码也是这么写的。为什么用左闭右开因为这样可以避免mid归属的歧义也跟 Python 的切片习惯、range的习惯一致写起来少一份心智负担。整个算法可以理解为递归地把问题尺寸对半砍直到砍成不可再分的单元素然后从最底层开始一层层把有序小块合并成有序大块。递归时是自顶向下地拆真正排序发生在合并时是自底向上地合。2.2 一次 merge 到底做了什么假设已有两个有序数组 A 和 B准备一个空数组 C用三个指针分别指向 A、B、C 的当前位置。每一轮比较 A[i] 和 B[j]把更小的那一个放进 C同时对应指针后移。某一侧耗尽后把另一侧剩余元素整个追加到 C 尾部。因为 A、B 各自有序剩余部分也一定有序直接追加即可。这个循环每轮推进一个元素两个序列加起来长 n所以一次 merge 的时间是 O(n)。这里有一个写法上的细节必须强调比较条件要写成A[i] B[j]而不是A[i] B[j]。当两个值相等时优先取左序列的元素这样相等元素的先后顺序才不会被打破算法才能保持稳定。这个细节面试常考实际工程里要留住原始顺序时也是命门比如按“优先级”排序时想保留“提交时间”的顺序。2.3 复杂度推导这回算明白用递推公式来看归并排序设 T(n) 为对 n 个元素排序所需时间T(n) 2 * T(n / 2) O(n) 拆成两个 n/2 规模子问题 一次 O(n) 的 merge T(1) O(1)逐层展开第 1 层做 1 次 O(n)第 2 层做 2 次 O(n/2)合计还是 O(n)第 3 层做 4 次 O(n/4)合计仍是 O(n)。层数一共 log2(n) 层每一层合计都是 O(n)于是总复杂度 T(n) O(n log n)。无论数据本来有序还是完全逆序拆分的路径是一样的合并的工作量也一样因此最好、最坏、平均时间复杂度都是 O(n log n)。空间复杂度则需要分情况说。如果每次 merge 都新建一个临时数组那总的额外空间会达到 O(n log n)工程上普遍做法是只开一个和原数组等长的临时数组tmp所有 merge 都在同一个tmp里读写再加上递归调用栈深度 O(log n)空间复杂度收敛为 O(n)。这也是为什么实现归并排序时“临时数组只申请一次”是第一个要养成的习惯。2.4 归并排序的稳定性验证用一个具体例子验证稳定性数组[3a, 1, 3b]其中 3a 和 3b 值相同但代表不同记录。第一层切分得到[3a]和[1, 3b]右侧排序后为[1, 3b]3b 保持原位。合并时比较 3a 和 11 先入列再比较 3a 和 3b因为条件用了取左侧的 3a 入列最后 3b 入列。最终顺序是[1, 3a, 3b]3a 始终在 3b 前面稳定成立。如果条件写成右侧 3b 会先被选中3a 和 3b 的相对顺序就被颠倒了稳定性当场失效。3. 归并排序两种实现与边界细节3.1 递归版最直白但别写出“玩具代码”网上最常见的归并排序 Python 写法是这样的def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) 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这段代码逻辑上一点没错但假如你要拿它去处理 100 万元素性能会很糟糕。原因在于每次递归都切片arr[:mid]和arr[mid:]各复制一份递归每一层都在复制时间、空间都被白白浪费。正确姿势是始终在原数组上用索引操作只准备一个全局tmpdef merge_sort_inplace(arr): n len(arr) tmp [0] * n def split_and_sort(left, right): if right - left 1: return mid (left right) // 2 split_and_sort(left, mid) split_and_sort(mid, right) merge(left, mid, right) def merge(left, mid, right): i, j, k left, mid, left while i mid and j right: if arr[i] arr[j]: tmp[k] arr[i] i 1 else: tmp[k] arr[j] j 1 k 1 while i mid: tmp[k] arr[i] i 1 k 1 while j right: tmp[k] arr[j] j 1 k 1 arr[left:right] tmp[left:right] split_and_sort(0, n) return arr注意两个细节。其一merge函数入参是(left, mid, right)三个边界分别表示左半区间[left, mid)和右半区间[mid, right)这种“半开区间”贯穿全文别混成闭区间。其二每次 merge 开始前不需要清理tmp中其他位置因为最后只把[left, right)这一段拷贝回去其他位置的脏数据不影响结果。3.2 迭代版自底向上绕开递归递归版虽然思路清晰但深层调用在某些语言里可能有栈风险。迭代版从宽度入手先把数组看成 n 个长度为 1 的有序块然后把相邻两个块两两合并得到长度为 2 的有序块再合并成长度 4 的有序块宽度翻倍地往复直到整个数组有序。def merge_sort_iter(arr): n len(arr) tmp [0] * n width 1 while width n: for left in range(0, n, width * 2): mid min(left width, n) right min(left width * 2, n) i, j, k left, mid, left while i mid and j right: if arr[i] arr[j]: tmp[k] arr[i] i 1 else: tmp[k] arr[j] j 1 k 1 while i mid: tmp[k] arr[i] i 1 k 1 while j right: tmp[k] arr[j] j 1 k 1 arr[left:right] tmp[left:right] width 1 return arr这个版本没有递归调用纯用循环控制宽度逻辑上更贴近 merge 的本质真正干活的永远只有 merge 这一步其他都是在安排 merge 的顺序。mid和right的min()是为了处理数组末尾凑不齐一整块的情况这也是迭代版最容易写错的地方。外层宽度可能很大但left width * 2可能越界不截断的话取到的mid、right会越过数组边界。3.3 最容易翻车的三个边界问题第一mid计算。用(left right) // 2时left 和 right 都很大可能会溢出吗在 Python 里不会在 C/Java 里如果 left 和 right 都是接近 INT_MAX 的整数left right可能溢出要写成left (right - left) // 2。这个习惯养成了能省一轮排查。第二递归终止条件。right - left 1表示区间只剩 0 个或 1 个元素直接返回。如果写成 1一旦传入空区间会死循环或越界。虽然递归调用时通常不会出现空区间但防御性写法更稳妥。第三merge 循环结束后的清理。两个 while 分别负责把左侧剩余、右侧剩余搬到tmp最后统一arr[left:right] tmp[left:right]。有人为了省事直接把左剩余写成tmp[k:mid] arr[i:mid]这样又会触发切片复制性能掉一截。for 循环逐个搬运虽然看着啰嗦但在性能敏感的场景里更靠谱。4. 工程优化让归并排序能打满全场4.1 小数组切换插入排序递归一直拆到单元素才返回切分的次数非常多而元素很少时函数调用开销占比高。工程上通用的优化是设一个阈值通常是 16 到 32当区间长度小于等于阈值时直接改用插入排序。插入排序在近有序的小区间上很快常数因子极小正好填补归并排序在“小块”阶段的开销。THRESHOLD 32 def merge_sort_opt(arr): n len(arr) tmp [0] * n # 先对每个长度为 THRESHOLD 的小块做插入排序 for start in range(0, n, THRESHOLD): end min(start THRESHOLD, n) for i in range(start 1, end): key arr[i] j i - 1 while j start and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key # 从 THRESHOLD 宽度开始两两归并 width THRESHOLD while width n: for left in range(0, n, width * 2): mid min(left width, n) right min(left width * 2, n) if arr[mid - 1] arr[mid]: continue i, j, k left, mid, left while i mid and j right: if arr[i] arr[j]: tmp[k] arr[i] i 1 else: tmp[k] arr[j] j 1 k 1 while i mid: tmp[k] arr[i] i 1 k 1 while j right: tmp[k] arr[j] j 1 k 1 arr[left:right] tmp[left:right] width 1 return arr这里还多做了一步优化if arr[mid - 1] arr[mid]: continue。当左半区间的最后一个元素已经小于等于右半区间的第一个元素时说明这两个区间天然有序不需要 merge。对接近有序的数据这一步能省掉大量无谓的复制。4.2 临时数组复用与拷贝方向很多人写归并排序会忽略一个性能问题每层 merge 都往tmp写写完再拷回arr。这等于每个元素每次合并要拷贝两次。更讲究的做法是“乒乓式”拷贝这轮从arr读、往tmp写下轮从tmp读、往arr写用奇偶层数切换读写方向最终把“写回”这一步完全抵消。但这个优化会显著增加代码复杂度普通场景下“申请一次 tmp 一次性拷回”已经够用性能瓶颈通常不在这里。真正的坑是“每层都 new 一个临时数组”这在 Java、C 里尤其致命。归并排序空间复杂度 O(n) 的前提就是只用一个临时数组如果每次递归都new int[n]内存峰值直接变成 O(n log n)百万级数据就可能 OOM。4.3 链表上的归并排序不用额外存储数组归并需要 O(n) 的额外空间但链表可以做到 O(1) 额外空间因为合并链表只需要改指针。找链表中点用快慢指针慢指针每次走一步快指针每次走两步快指针到链表尾时慢指针正好在中点。中点之后断开递归排序两条子链表最后用双指针原地合并。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def merge_sort_list(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 merge_sort_list(head) right merge_sort_list(mid) return merge_two(left, right) def merge_two(l1, l2): dummy ListNode() cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next这里的坑在快指针的初始化fast head.next而不是head。如果fast head偶数长度链表找到的中点会偏向右侧断链后左右子链表长度不均匀不影响正确性但会让递归深度和性能平衡变差。用head.next可以让慢指针停在左半边的末尾断出的左右两半长度更均衡。4.4 外部排序归并是磁盘整理的灵魂当要排序的数据超过内存容量时整个排序思路都得变。外部排序的标准做法是把大文件切成若干能装进内存的小块每块各自排序后写回磁盘形成一批“已排序的小文件”最后用多路归并把它们合并成一个大文件。这里多路归并如果只是两两合并小文件数量很多时会反复读写磁盘所以工程上都用“败者树”或“堆”来做 K 路归并一次从 K 个文件中各取一个当前最小记录选出全局最小输出。这个机制和内存中的归并排序是同一个灵魂只是“数组元素”换成了“文件里的记录”。5. 常见问题与排查技巧实录5.1 递归太深会栈溢出吗先算笔账对 10 亿个元素排序递归深度是 log2(10^9)约 30 层。这个深度对绝大多数语言远谈不上栈溢出。真正让 Python 报RecursionError的是本节开头那种“每层切片”的写法——虽然在递归终结前不会超过限制但每一层都可能因为复制导致额外的层级判断和内存压力。所以结论是只要用索引 全局 tmp 的实现递归深度根本不是问题如果实在对递归有顾虑用迭代版最省心。5.2 内存开销比想象中大有人在评估时把归并排序的空间复杂度记成 O(1)这是和堆排序搞混了。归并排序必须有一个缓冲区才能完成两个有序序列的合并这个 O(n) 空间是绕不开的。如果面试官或项目要求“原地排序”归并排序不是好答案快速排序才是。但反过来如果系统里有足够内存、且稳定性和最坏时间有硬要求归并排序的 O(n) 空间是值得付的代价。曾经有个数据管道项目我对千万级记录做稳定排序时选了归并内存峰值比预想多了几十 MB但换来了线性的可预期耗时整体很值。5.3 归并还是快排这题没有标准答案维度归并排序快速排序平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n log n)O(n²)空间复杂度O(n)O(log n)原地版稳定性稳定常不稳定缓存友好性较差随机写临时数组较好原地交换适合场景链表、外部排序、稳定性要求高内存紧张、普通数组排序个人经验在 JDK 和 Python 的内置排序里真正跑在底层的是 Timsort它本质上是“归并排序 插入排序”的混合体同时检测数据中已有的有序片段run直接利用这些天然有序结构。所以日常开发直接用内置sort()往往是最优解自己手写归并排序的场景主要是学习原理、处理自定义结构、或者做外部数据归并。5.4 大量重复元素反而变慢如果数组里全是同一个值普通归并排序每一层都会完整地做合并和拷贝实际上全是无用功。Timsort 会先识别 run如果整个数组已经有序直接一次遍历就结束。手写归并时可以加一个类似检测if arr[mid - 1] arr[mid]: continue上一节优化里已经包含。如果重复元素非常多又想极致优化可以考虑把 merge 改成“跳过相等区间”的方式但收益在多数业务场景下有限不值得为此牺牲代码可读性。6. 实战用多路归并整理三个有序日志文件6.1 问题描述与方案设计回到开头那个需求三个日志文件log1.txt、log2.txt、log3.txt每行是“时间戳 空格 日志内容”每个文件内部按时间戳升序排列。目标输出一个全量时间线文件所有行按时间戳全局升序内存占用最好控制在几十 MB 以内。最简单的思路是全读进内存排序但假如每个文件 300 万行、平均行长 100 字节总数据接近 900MB对服务器内存是个不小的压力。更合理的方案是 K 路归并同时打开三个文件各取当前第一行放入最小堆每次从堆中弹出最小行写入输出文件再从该行来源文件读入下一行补进堆。因为每个文件自身有序堆里始终维护的是 K 个文件的“当前最小候选”弹出来的自然是全局最小。6.2 用 heapq 实现最小堆 K 路归并import heapq def merge_sorted_files(file_paths, output_path): readers [] heap [] for idx, path in enumerate(file_paths): f open(path, r, encodingutf-8) readers.append(f) line f.readline() if line: heapq.heappush(heap, (line, idx)) # 以整行字符串比较时间戳前缀保证正确顺序 with open(output_path, w, encodingutf-8) as out: while heap: line, idx heapq.heappop(heap) out.write(line) next_line readers[idx].readline() if next_line: heapq.heappush(heap, (next_line, idx)) for f in readers: f.close()为什么可以直接用字符串line参与堆比较因为每行都以固定格式的时间戳开头比如2024-01-15 10:23:45 ...字符串比较在相同格式下正好等价于时间比较。如果时间戳格式不统一就得先把时间戳解析成元组放进堆例如heapq.heappush(heap, (timestamp_tuple, idx, line))。堆里(line, idx)是用行文本和文件编号一起入堆的这样万一有两行的字符串完全一样堆也能通过 idx 区分它们不会因为比较tuple时撞到重复元素而报错。这个脚本处理 90 万行日志实测约几秒完成内存占用基本等于堆大小加上每行字符串的缓冲远小于 900MB 的全量读入方案。6.3 常见问题输出顺序丢失、堆元素比较失败第一次写完这个脚本时我踩过一个相对隐蔽的问题日志文件里如果出现空行readline()返回\n空字符串会和正常行一起进堆导致输出文件头部多出一堆空行。解决办法是在读入时加个过滤if not line.strip(): continue同时要考虑文件末尾可能没有换行符的情况用if line:判断已经覆盖了这种情况。另一个问题是heapq的元组比较如果入堆的(line, idx)中 line 相同会比较 idx没问题但如果直接入堆line两个完全相同的行比较也没问题。真正会翻车的是把时间戳解析成float或datetime后混入None或非法值。所以送入堆的数据类型要统一要么全用字符串要么统一转成 tuple不要混搭。6.4 扩展到更多路K 值变大怎么优化如果待合并的文件从 3 个变成 300 个堆的大小变成 300每次弹堆和入堆的复杂度是 O(log 300)仍然完全可接受。K 路归并的瓶颈通常不在堆而在磁盘 IO每次只读一行会导致大量小 IO。优化方向是给每个文件加缓冲读取用io.BufferedReader或者自己维护一个读取队列让每次readline()都能从内存缓冲区拿数据减少系统调用次数。更激进的做法是每个文件一次读入一批行比如 4096 行排序好后按批次送入堆批内有序批间堆排序基本可以说是“退化成外部排序”了。7. 用个人体会收个尾归并排序是我在工作中学到的最“值”的算法之一。它不像快排那样有那么多花哨的分区技巧也不像堆排那样需要呵护堆结构它靠的是一个朴素到极致的动作把两堆有序的东西合并成一堆。而这个动作几乎出现在所有“整理”场景里合并有序日志、数据库归并连接、外部排序、Timsort 底层、MapReduce shuffle 阶段……好像哪里都有它。我自己现在写归并排序默认就直接上迭代版加小数组插入优化因为不用关心递归深度逻辑也能一眼看穿。遇到“多个有序源合并成一个结果”的需求第一反应就是堆做 K 路归并。如果你刚开始学也别急着背代码先拿两叠扑克牌在桌上合一次把那个手感找到代码里所有边界条件就都变得顺理成章了。最后补一个实用小技巧凡是归并相关的实现我都建议第一步先画区间图把[left, mid)和[mid, right)画在纸上标清楚每个指针的起始位置和终止位置再动手写代码。这个习惯帮我避免过至少十次边界条件导致的线上故障希望你也能用上。