刚接触 STL 那阵子我一直觉得std::merge是个可有可无的算法。原因很简单它要求输入已经有序那我直接先合并再 sort 一下不也一样直到有一次线上功能需要把十几个按时间排序的日志分片合并成一个大文件数据量达到几十个 G我才意识到 merge 这类算法的真正分量。同样是生成一份有序结果sort 需要反复比较和搬移merge 却能顺着已经排好的序一路推进到底中间不需要额外的排序开销。这篇文章不是对 cppreference 的复述我更想把它写成一份实战笔记merge 的适用边界、函数签名、内部执行机制、容易混淆的近亲算法以及我实际用过的几种合并方案。写 C 三四年的同学应该能直接拿走用刚入门的朋友看复杂度推导和稳定性那几段也能建立正确的直觉。1. 先搞清楚一个问题merge 只处理已经有序的数据1.1 merge 解决的是哪类问题std::merge的语义可以概括成一句话把两个已经按同一规则排好序的输入范围合并成一个新的有序范围。关键前提是“已经有序”它不会帮你排序也没法对乱序数据做任何修正。你把两个乱序的容器丢进去得到的结果大概率还是一个乱序容器甚至merge 过程中由于等价元素的处理方式不同输出序列会比输入更难看。那现实里什么时候会有“现成的有序数据”场景其实非常多。比如分页接口返回的数据每一页都按时间戳排好序下一页回来之后直接合并进已有列表就不需要重新 sort。再比如日志系统把一天的数据切成多个分片每个分片内部按键值排序最终交付给下游时需要合并成一个完整的有序文件。还有外部排序的归并阶段内存放不下全量数据只能在磁盘上保留若干有序临时文件最后用 merge 把它们合并成最终结果。这些场景的共同特点是顺序信息已经存在不需要再花 O(N log N) 的代价去恢复秩序。所以 merge 并不是 sort 的下位替代它解决的是另一类问题多个有序子集的合并。这个区分很重要因为它直接影响你选算法时的心态——如果你手里的数据是无序的老老实实 sort如果数据恰好有序只是分散在多处merge 才是正确工具。1.2 为什么别用 sort 一把梭有人会说合并两个有序 vector我直接vector.insert再std::sort不就行了数据量小的时候这样确实无所谓。但数据量一旦上来差距就非常明显。sort 是原地排序不产生额外的输出容器但是平均时间复杂度是 O(N log N)。merge 呢它只需要线性扫描两个输入每次比较至少能确定一个元素的最终位置总时间复杂度是 O(N)。假设两个序列各有 500 万个元素合并在一起是 1000 万。如果用 sort 全量排序比较次数大概是 1000 万乘以 log2(1000万)也就是两亿多次比较而 merge 只需要大概 999 万次比较。数量级差了一个 log在日志合并、外部排序这类 IO 密集场景里这差距会直接反映在最终运行时间上。另外一个常被忽略的点是稳定性。std::sort不保证相等元素的相对顺序std::stable_sort保证但代价是更高的空间开销。std::merge天然稳定两个输入范围内等价的元素输出时第一个范围内的元素会排在第二个范围元素的前面。如果你的业务逻辑依赖这种先后关系merge 能给你一个明确、可预测的结果。当然merge 也有自己的代价它需要一块额外的输出空间不能完全原地工作。这一点放到后面“输出空间”那节详细展开。选型时可以记一张大概的对照表备查数据现状推荐做法原因整体无序需要排好sort或stable_sort先给数据建立秩序多个有序范围需要完整合并std::merge线性、稳定、语义清晰合并时希望去重set_union等价组只保留一个元素同一容器前后两段各自有序inplace_merge原地合并省空间链表上的大对象合并std::list::merge节点转移零复制2. 函数签名与调用前必须确认的三个条件2.1 完整签名和返回值标准库里和我们打交道最多的两个版本是这样的template class InputIt1, class InputIt2, class OutputIt OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first); template class InputIt1, class InputIt2, class OutputIt, class Compare OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp);InputIt1和InputIt2可以是不同类型的迭代器这也意味着你完全可以把vectorint和listint的迭代器混着传只要元素类型能互相赋值。d_first是输出迭代器函数执行完返回一个指向输出范围最后一个被写入元素之后位置的迭代器。这个返回值在你需要链式操作时很有用但大多数场景下直接忽略它也不会出事。C17 增加了带执行策略的并行重载C20 又加入了std::ranges::merge后面实战章节会单独挑 ranges 版本讲。单论经典版本需要把注意力放在三个地方输入是否有序、输出空间是否够、比较器是否一致。这三条任何一条出问题程序都不会给你正常的报错更多是静默产出坏数据或者干脆崩溃。2.2 输出空间merge 从不帮你开内存merge 只是把元素“写”到d_first指向的位置它自身不负责申请内存。这是初学者最容易踩的坑。我见过不少类似这样的写法std::vectorint out; // 空 vector std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());这段代码是未定义行为。out为空out.begin()相当于一个悬空的输出位置merge 会把元素写到不属于任何容器的内存上去。Debug 模式下容器迭代器还有可能帮你拦一下Release 下就是静默内存破坏表现为随机崩溃或者数据被悄悄改掉。正确姿势有两种。第一种是先预留空间再配合back_inserterstd::vectorint out; out.reserve(a.size() b.size()); std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));第二种更直接先resize好目标大小然后传入普通迭代器std::vectorint out(a.size() b.size()); std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());两种都是稳妥的。区别在于第一种在合并过程中会多次检查容量并可能触发 vector 扩容第二种一次性分配完内存布局更紧凑。数据量大时我会倾向于resize版本数据量小或者想少写一行reserve back_inserter也行。另一个容易被忽略的禁忌是merge 的输出范围不能和任何一个输入范围重叠。标准明确说这是未定义行为。所以如果你想“原地 merge”直接用std::inplace_merge不要试图用std::merge把输出写到输入的位置上。2.3 比较器两个输入必须遵守同一套规则默认情况下 merge 使用operator也就是按升序合并。如果你想按降序合并需要传入std::greater之类的比较器std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out), std::greaterint());这里有一个很容易被忽略的连带要求两个输入范围必须也按同一个比较器有序。比如你给 merge 传了std::greaterint()那么 a 和 b 都必须是递减的否则合并结果不会整体有序。对于结构体常见的做法是写 lambda。比如按某个业务序号合并struct Record { int seq; std::string data; }; auto cmp [](const Record x, const Record y) { return x.seq y.seq; }; std::merge(ra.begin(), ra.end(), rb.begin(), rb.end(), std::back_inserter(out), cmp);比较器还必须满足严格弱序。也就是说如果cmp(a, b)为假且cmp(b, a)也为假那么 a 和 b 被视为等价。在中国程序员的日常里最典型的反例就是“相等时返回 true”这种失误比如return x.seq y.seq。这种比较器破坏了严格弱序轻则让 merge 输出顺序不符合预期重则在某些标准库实现下直接掉进死循环或越界访问。大家在排序时代可能对这条规则有点印象但合并时代经常因为写得太顺手就忘了。3. 执行机制拆解线性比较、稳定性、剩余段的处理3.1 核心循环和等价元素的先后merge 的内部实现虽然各标准库略有差异但核心逻辑基本等价于下面这段手写循环while (first1 ! last1 first2 ! last2) { if (*first2 *first1) { *d_first *first2; first2; } else { *d_first *first1; first1; } d_first; } d_first std::copy(first1, last1, d_first); d_first std::copy(first2, last2, d_first);注意分支条件的写法这里用的是*first2 *first1不是*first1 *first2。这是一个细节中的细节。当两个元素等价时也就是*first2 *first1为假 且*first1 *first2也为假merge 会选择输出第一个范围中的元素。这正是稳定性语义的来源。如果你写成if (*first1 *first2)那么当两个元素相等时你会输出第二个范围中的元素第一个范围里的等价元素被留到了后面稳定性就被破坏了。看上去只是差不多的几个字符但标准里白纸黑字写明了 merge 是稳定的用错条件会产出和文档完全不符的结果。我的建议是在不知道哪个元素“更小”的时候无条件偏向第一个输入范围这是最安全的实现方式。另外值得一说的是最后的两个std::copy。merge 过程中只要有一边用完了另一边剩余的所有元素可以直接整体拷贝到输出尾部不需要再逐个比较。很多人手写归并时容易漏掉这段结果丢元素。STL 把这个边界处理封装好了你只要无脑传迭代器就行。3.2 复杂度推导N 次比较的由来merge 的时间复杂度为什么是 O(N)我们直观推一下。每一轮 while 循环会做一次比较然后至少把一个元素写入输出。也就是说比较次数不会超过写入元素的总数减一。为什么是减一因为最后一次比较结束后有一方已经到达末尾之后剩下的元素全部通过std::copy直接搬运不再需要比较。举个例子a{1, 3, 5}b{2, 4, 6}。合并过程大致是比较 2 和 1输出 1比较 2 和 3输出 2比较 4 和 3输出 3比较 4 和 5输出 4比较 6 和 5输出 5然后剩余 6 直接拷贝。算下来 5 次比较等于 33-1也就是 n1n2-1。如果两个序列长度差距很大比较次数会更少因为短序列耗尽之后剩下的全是拷贝。因此merge 的最坏情况就是 n1n2-1 次比较时间复杂度 O(N)不计算输出空间的话额外内存占用只有 O(1)。这个开销对于排序来说非常漂亮。这里也解释了为什么在外部排序里 merge 是最后的收尾动作每一轮扫描都是线性的而外部排序里磁盘 IO 才是真正的瓶颈merge 可以把磁盘读写的次数压在很低的水平。3.3 输入迭代器带来的流式合并能力merge 对输入迭代器的最低要求是InputIterator这意味着你不必把数据完整加载到内存中就可以完成合并。std::istream_iterator就是一个典型的输入迭代器它可以从文件流里一个值一个值地读。于是我们可以在两个有序文件之间直接做一次“流式合并”std::ifstream f1(part1.sorted); std::ifstream f2(part2.sorted); std::istream_iteratorint b1(f1), b2(f2), eof; std::ofstream out(merged.sorted); std::merge(b1, eof, b2, eof, std::ostream_iteratorint(out, \n));代码里的b1和b2每次被 merge 推进时内部都会从对应文件读一个新值。整个过程内存里只保存少数几个元素两个文件被逐行消费最后生成一个完整的有序大文件。这个套路就是外部归并排序里“归并阶段”的标准实现。手写这种流式归并并不难但要处理文件 IO、迭代器状态、末尾判断等一堆细节用标准库的 merge 配合istream_iterator代码量骤然减少而且逻辑几乎不会错。4. 别把 merge 和近亲搞混inplace_merge、set_union、list::merge4.1 inplace_merge原地合并同一容器的两段std::merge把两个独立范围写到第三个范围std::inplace_merge则是把同一个容器内相邻的两段有序数据原地合并成一段整体有序数据。它的签名大概是这样的template class BidirIt void inplace_merge(BidirIt first, BidirIt middle, BidirIt last);前提条件是[first, middle)和[middle, last)都已经被排好序。举个例子std::vectorint data{1, 3, 5, 2, 4, 6}; std::inplace_merge(data.begin(), data.begin() 3, data.end()); // data 变成 {1, 2, 3, 4, 5, 6}它的复杂度比较微妙。如果有额外内存可供临时缓冲区使用那么是 O(N) 次比较、O(N) 次移动如果一点额外内存都分不到标准库实现会退化成更复杂的算法最坏情况下是 O(N log N) 次移动。所以它非常适合做归并排序的“归并”这一步也适合在同一个向量里前一半和后一半各自有序时省掉新建容器直接整理。我实际工作中用它的场景是游标翻页后的数据合并。某次旧接口返回多页数据每页内部有序翻页完成后用户要求整体有序展示我直接把所有页的数据拼进一个 vector然后对每相邻两组做inplace_merge比把整块数据重新 sort 要快尤其是内存充足的时候。4.2 set_union 家族去重语义和 merge 完全不同从名字上看set_union和merge很像都是输入两个有序范围产出一个有序范围。但它们的核心语义差异在于重复元素的处理。merge 会把两个输入里的每一个元素都保留下来哪怕两个序列里有完全相同的值。set_union则会把等价元素视为同一个逻辑元素只往输出里写一份。看个例子std::vectorint a{1, 2, 2, 2}; std::vectorint b{2, 3}; std::vectorint merged; std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(merged)); // merged: 1, 2, 2, 2, 2, 3 std::vectorint unioned; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(unioned)); // unioned: 1, 2, 3这里最直观的区别看出来了merge 把四个 2 全部保留set_union 只保留一个 2。实际业务里如果你是在做集合运算统计去重后的数量选 merge 就是灾难如果你是在做数据拼接选 set_union 则会莫名丢掉重复记录。顺便把 set 家族其他成员也一起整理清楚算法输出内容典型用途std::merge两个范围的全部元素重复都保留完整有序合并std::set_union两个范围的并集等价元素去重集合求并std::set_intersection同时出现在两个范围的元素集合求交std::set_difference出现在第一个但不在第二个的元素集合求差这些算法都要求输入有序也都支持自定义比较器但语义天差地别选错了不会报错只会让结果数字不对。4.3 std::list::merge不复制元素节点直接转移std::list和std::forward_list各自有一个成员函数merge它和算法版本的std::merge有一个本质区别成员版本通过调整节点指针来合并两个链表不复制任何元素数据。这意味着对于std::string、自定义结构体等“重类型”元素成员 merge 的性能优势非常明显。std::liststd::string l1{apple, orange}; std::liststd::string l2{banana, peach}; l1.merge(l2); // l1: apple banana orange peach // l2: 空列表和算法版本一样调用前需要保证两个链表都已经有序并且使用同一个比较规则。成员 merge 还有一个特点调用后传入的链表l2会变空所有节点被物理转移到l1中。这个行为跟merge算法复制元素完全不同如果你还保留着l2的迭代器这些迭代器在l1.merge(l2)之后仍然有效指向的节点已经归属到l1名下用例较少但有印象总比将来遇到时满头问号强。成员 merge 的复杂度是 O(N) 次比较节点移动本身是常数时间。因此链表合并大对象时我优先用成员函数而不是算法版本。5. 实战连续分片合并成一个有序结果的三种做法5.1 两个 vector 合并的标准姿势最常规的用法就是把两个有序std::vector合并成一个新std::vector。建议直接预留好空间再合并std::vectorint a{1, 3, 5, 7}; std::vectorint b{2, 4, 6, 8, 9}; std::vectorint out; out.reserve(a.size() b.size()); std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));这里为什么要reserve因为back_inserter每次 push_back 都可能触发容量检查。数据量小的时候无所谓但如果是几十万元素的 vector反复扩容带来的搬移开销不可忽视。提前reserve让 vector 一次性分配够内存后续所有写入都不需要再检查容量也更配合 CPU 缓存。如果元素类型是std::string这种持有堆内存的类型reserve 减少的搬移成本更为可观。比较器这里默认用两个输入都必须是升序。如果业务数据是降序就改用std::greaterint()同时保证两个输入也是降序。这个规律前面已经说过不再重复。5.2 多路归并优先队列还是两两归并实际工程里很少只有两个分片。更多情况是你有 k 个有序 vector希望合并成一个完整有序 vector。两种常见的思路如下。第一种是两两归并。把第一个和第二个合并成新 vector再用结果去和第三个合并以此类推。实现最简单每个分片的数据会被反复扫描多次总复杂度是 O(kN)。k 很小比如 2~4的时候这种办法通常最快因为它的访问模式对缓存友好实现里没有额外的堆结构开销。第二种是用优先队列做 k-way merge。思路是维护 k 个当前候选元素每次从堆顶取出最小值写入输出然后从对应分片里推进一个元素。总复杂度是 O(N log k)。当 k 比较大或者你不想每次都生成中间 vector 时这种方法更合适。核心思路大概是std::priority_queueNode, std::vectorNode, std::greater pq; // Node 里保存当前值、所属分片号、分片内的当前位置 // 初始化时把每个分片的第一个元素入堆 while (!pq.empty()) { auto cur pq.top(); pq.pop(); output.push_back(cur.value); if (cur.hasNext()) { pq.push(cur.next()); } }这里不展开完整实现了因为细节取决于数据结构和分片存储方式。但可以记住一个原则分片数量少时优先两两归并分片数量多或者内存有限希望边读边写时用优先队列做多路归并。这个选题思路在很多分片导出、外部排序场景里都适用。5.3 C20 ranges::merge 与投影如果项目已经是 C20可以尝试std::ranges::merge。它的最大亮点是支持投影函数可以直接按对象成员合并不用手写 lambdastruct Record { int seq; std::string data; }; std::vectorRecord a{{1, one}, {3, three}}; std::vectorRecord b{{2, two}, {4, four}}; std::vectorRecord out; std::ranges::merge(a, b, std::back_inserter(out), std::less{}, Record::seq, Record::seq);这个调用里的Record::seq就是投影merge 在内部比较前会先取出成员的seq而不是比较整个结构体。如果比较逻辑比较复杂也可以继续用 lambda。ranges 版本的返回值是一个merge_result结构里面包含三个迭代器第一个输入里未被消费的位置、第二个输入里未被消费的位置以及输出末尾。如果你要做流式合并这个返回值让你知道剩下哪些数据还没处理。不过坦白说新项目里用 ranges 很爽老项目里为了风格统一我还是经常用经典版本。大家根据自己的实际环境取舍不要为了新特性强行引入。5.4 外部归并的最后一步文件流合并前面第 3 章简单提过文件流合并这里单独展开一下因为它确实是 merge 在工程领域最能打的场景之一。当数据大到内存装不下时常见的套路是把大文件分成好几个 chunk分别排序后写到磁盘临时文件。最后把多个有序临时文件合并成一个完整文件。这个“最后合并”正是 merge 的舞台。两个文件合并的代码前面已经给过。如果要合并的临时文件不止两个可以用一个更通用的循环每次把当前已合并结果和下一个临时文件再 merge。这样虽然会多读几遍中间文件但胜在实现简单、稳定。真正完整的多路文件归并也可以基于std::istream_iterator配合优先队列来做。每个输入流对应一个迭代器堆里比较的是各迭代器当前指向的值每次弹出最小值后推进对应迭代器再把新值入堆。由于每个文件的数据都在磁盘上性能瓶颈在磁盘 IO比较次数多那么一点通常不会成为首要问题。在很多离线数据处理流程里这一套模板我用了很多年几乎没有翻过车。6. 踩坑记录用坏过 merge 才记得住的细节6.1 输出空间不足和输入输出重叠都是静默炸弹把输出迭代器接到一个空容器的begin()上是最早我犯过的错。当年合并两个列表写出来的程序在 Debug 下崩溃Release 下运行得“好好的”但最终结果缺数据。查了很久才发现是out没有预先分配空间直接在out.begin()上狂写内存早就越界了。所以现在只要看到 merge 的输出迭代器传的不是back_inserter或resize出来的迭代器我都会多留一个心眼。另一个静默炸弹是输入输出重叠。有人觉得std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v1.begin())应该能原地合并两个 vector实际上这是未定义行为。merge 边读边写时很可能会覆盖掉还没读取的原数据。如果你确实想复用第一个容器的空间先把结果写进临时 vector再 move 回去或者用inplace_merge处理同一容器内部的两段。6.2 move-only 元素没法直接用 merge标准里 merge 的语义是复制元素它要求输出迭代器的 value_type 能接收来自输入迭代器的值。对于std::unique_ptr这种只能移动、不能拷贝的类型直接调用std::merge会编译失败。有人会想merge 内部用移动赋值不就好了抱歉标准没有提供 move 版本的std::merge。如果你需要合并std::vectorstd::unique_ptrT手写一个基于std::move(*it)的归并循环是更直接的办法。遇到这种需求别硬套 STL 算法合适的时候手写几行反而是最清晰的。6.3 合并前的断言与比较器一致性检查merge 的一个隐蔽陷阱是输入数据其实并不是按你传入的比较器排序的。比如某日志分片大部分按时间升序但其中一个分片因为历史遗留问题实际是降序合并完成后的输出在局部区域会出现倒序。这个问题的可怕之处在于它不会报错只有数据被下游消费时排序异常才会被发现。我的习惯是在合并前加断言assert(std::is_sorted(first1, last1, comp)); assert(std::is_sorted(first2, last2, comp));std::is_sorted本身也是线性的多一次扫描在绝大多数场景下可接受。Debug 阶段打开断言Release 阶段如果性能敏感可以关掉。这一行断言配上统一的比较器几乎能挡住所有“输入不满足前提”的坑。6.4 我的使用习惯和收尾建议写了几年 C现在处理有序合并时我的选择基本是固定的普通容器跨范围合并用std::merge同一容器内部两段有序用std::inplace_merge链表大对象用成员merge新代码里按字段投影就用std::ranges::merge。每次调用前加断言检查输入有序输出端提前分配好空间。这套习惯看着琐碎但确实是在生产环境里救过我多次的东西。最后再说一个实际经验如果 merge 的结果看起来不对别急着怀疑标准库。先确认两个前提——输入是否真的有序、输出空间是否真的足够——这两个问题解决了merge 基本不会让你失望。可能这就是这类经典算法最好的状态简单、快、稳却需要你认真对待它。