【数据结构】归并与外排序

【数据结构】归并与外排序

🔥 H.莓飛： 个人主页

❄️个人专栏：「C++」「数据结构」「Linux系统编程」

✨ 心不畏死，踏屍前行。

📦 代码仓库：cocatrice_csdn_code

📖 博主简介：

概览

• 递归与非递归两种归并写法
• 临时数组与它的空间代价
• 相等取左边
• 内外分界如何决定

核心知识

一、简述

前面十几篇里，排序的动作要么是拿一个元素往回找位置，要么是在区间里来回换，都比对过元素之间的大小关系。归并换了个角度：它先假设手上已经有两段排好序的数据，只负责把这两段拼成一段。

拼的过程非常朴素，两段各放一个游标在队头，每次比较两个队头的值，小的那个搬进结果，游标往后走一格，直到某一段搬空，剩下的那一段直接整体接上去。拿 1 4 7 和 2 3 9 走一遍，先比 1 和 2 取 1，再比 4 和 2 取 2，接着比 4 和 3 取 3，然后 4 比 9 取 4，7 比 9 取 7，最后左边空了把 9 接上，得到 1 2 3 4 7 9。

图 1 两个有序段并成一段，每一步只比两个队头

这个动作的代价可以数得很准：每搬一个元素最多比一次，输出 N 个元素就最多比 N 减一次；两个游标只往右走，谁都不回头。跟插入排序那种要往回挪的做法比，合并完全不吃数据原来的顺序，一段随机数据的两个有序段，合并起来跟两段完美数据的合并是一个速度。

真正有用的地方在于它可以自己套自己，也就是同一句话能用在更小的规模上。手上只有一堆乱序数据、没有现成的两段有序段的时候，那就把整段切成两半，让两半各自先排好，再合起来。两半怎么排好，还是同一句话：再切两半，先排好再合。切到只剩一个元素的时候它天然有序，这一层就不用做了。于是整个排序变成先递归往下切、再逐层往上合的过程。

二、递归法

递归的写法跟二叉树的后续遍历一个形状：先处理左半，再处理右半，最后才是自己这一步合并。合并这一步要一块地方存中间结果，因为两个有序段挨在一起放在原数组里，直接往原位置写会覆盖掉还没搬的元素。这块地方就是临时数组，长度跟原数组一样，在排序开始之前申请一次，整个递归过程里反复用。

图 2 递归归并：先分到只剩一个，再一层层并回来

/* 把 [left, mid] 与 [mid + 1, right] 两段并成一段 */staticvoidMergeArr(int*a,intleft,intmid,intright,int*tmp){inti=left;intj=mid+1;intk=left;while(i<=mid&&j<=right){if(a[i]<=a[j])/* 相等时先取左边，稳定性就靠这个等号 */{tmp[k++]=a[i++];}else{tmp[k++]=a[j++];}}while(i<=mid){tmp[k++]=a[i++];}while(j<=right){tmp[k++]=a[j++];}memcpy(a+left,tmp+left,sizeof(int)*(right-left+1));}

临时数组申请在递归外面这一步值得单独说一句。合并的次数是 N 减一次，如果每合一回都去 malloc 一次 4MB，一百万条数据要走上百万次申请与释放，光是申请这块内存就够把整个排序拖成几秒；申请一次反复用，这一项开销就摊成了常数。

intMergeSort(int*a,intn){int*tmp;if(a==NULL||n<2){return0;}tmp=(int*)malloc(sizeof(int)*n);if(tmp==NULL){return-1;}MergeSortInner(a,0,n-1,tmp);free(tmp);return0;}

递归版的实测放在这台 CentOS 7 机器上跑，一百万个随机整数，每种写法跑三遍取最快的一次。递归归并 106.565 毫秒，同机的 qsort 是 126.475 毫秒；换成十万条，递归归并 8.948 毫秒、qsort 10.514 毫秒。归并比 qsort 快一截，原因之一是 qsort 要处理各种分布的防御性判断，归并对任何分布都是同一个流程。

同一批一百万条数据，归并跑出来的比较次数是 18675213，移动次数 19951424，而 N 乘以 log2 N 约等于 19931569。比较次数略小于这个数，因为每一层合并的时候，总有一段会先被搬空，剩下的那段直接接上，压根不用再比。

三、非递归法

递归版的好处是顺着思路写下来就行，坏处是要占调用栈，而且每一层都要判断边界。归并这件事其实可以用一个循环表达：不看什么递归树，只看段长。一开始认为每个元素自己是一段有序数据，段长是 1；然后把相邻的两段两两合并，段长变成 2；再两两合并，段长变成 4，一路翻倍到超过整个数组的长度就结束。

图 3 非递归归并：段长 1、2、4 一路翻倍

intMergeSortNonR(int*a,intn){int*tmp=(int*)malloc(sizeof(int)*n);intgap;for(gap=1;gap<n;gap*=2){inti;for(i=0;i<n;i+=2*gap){intleft=i;intmid=i+gap-1;intright=i+2*gap-1;if(mid>=n)/* 剩下的连左段都没凑满，这一轮不用并 */{break;}if(right>=n){right=n-1;}MergeArr(a,left,mid,right,tmp);}}free(tmp);return0;}

两处下标判断一个都不能少，因为数组长度不是二的幂的时候，最后一组经常凑不齐：mid 越过末尾说明右边连一段都没剩下，这一轮直接不用合；right 越过末尾说明右段短了一截，夹到 n 减 1 就行。少写第一个判断，循环会拿着一组不存在的数据去合并，读到的内存是数组之外的。

两版的实测结果贴在一起看：一百万条递归 106.565 毫秒、非递归 99.266 毫秒，十万条递归 8.948 毫秒、非递归 8.207 毫秒。非递归快一点点，省下来的是函数调用的开销与递归版的边界判断，差距不大，说明归并的耗时主要花在搬元素上，两种写法搬的次数完全一样。

两版对不对，用的办法是三方对照：同一批数据分别交给两版归并与 qsort，三方结果逐字节比较。九组典型数组（空、一个、升序、降序、重复值、带负数）、长度从 1 到 17 的每一组、五百组长度 0 到 60 的随机数组，全部一致，不一致 0 组。

四、稳定性

稳定性说的是关键字相等的两个记录，排完之后先后次序跟原来一样。归并能做到这一点，靠的是合并时那一行比较：左边队头小于等于右边队头，就先取左边。等于的时候也取左边，于是相等的一批记录里，原本在左边的那个一定先出，顺序不会被打乱。

图 4 相等的时候先取左边的，两个 3 的先后不会变

把带编号的记录塞进去跑一遍，谁保序谁不保序一眼就能看出来。原始数据是 5a 3b 5c 1d 5e 3f 2g，排完是 1d 2g 3b 3f 5a 5c 5e，三个 5 的先后还是 a、c、e，两个 3 的先后还是 b、f。把长度缩短到 2a 2b 1c，排完是 1c 2a 2b；3a 3b 1c 3d 排完是 1c 3a 3b 3d。递归版与非递归版跑出来是同一组结果，两版都保序。

归并的稳定性跟它的搬运方式有关，整个过程中它从不把两个元素直接对调，只把元素按原顺序抄进临时数组，再整段抄回来；抄的顺序由比较结果决定，相等时先抄左边，次序就保住了。前面那篇里选择排序之所以不稳定，正是因为它每趟都要拿最小值和第一位对调，一换就跨过了中间那些相等的元素。

稳定性在多关键字排序里很实用，比如一张表要先按分数排、分数相同按姓名排，做法是先按姓名排一遍，再用稳定的算法按分数排一遍；分数相同的那些记录保持姓名顺序，两趟下来两边都对。换成不稳定的算法，第二趟会把第一趟的成果打乱。

五、临时数组的长度

归并排序拿空间换时间，代价是一块跟原数组一样大的临时数组：一百万个 int 就是 4MB，一千万条就是 40MB。快排只需要递归栈的 log N 层，堆排序几乎是原地做，归并这一块空间省不掉，因为合并两个有序段的时候必须有一个地方暂存没搬完的结果。

图 5 归并的代价：额外的一块 N 个元素的数组

想省掉这块空间只能换数据结构，链表上的归并可以把两个有序链表直接接起来，只动 next 指针，额外空间是常数，第 19 篇会写这个做法；数组归并避不开这块空间，除非改用原地归并那种做法，代价是元素搬动次数暴涨，实际跑起来更慢。

工程上常见的选择是看数据规模，几十万条以内，4MB 的临时数组随手就有；碰到内存吃紧又需要稳定排序，就得掂量一下能不能接受这块开销，或者改成在磁盘上做外排序，把空间问题交给文件系统。

六、数据比内存大时方法

前面所有排序都有一个前提：数据全部躺在内存里，随机访问任何位置都是常数时间。数据量涨到内存装不下的时候，这个前提就没了，只能一块一块读进内存处理。这种数据在磁盘上、内存只放得下一部分的排序，叫外排序。

图 6 外排序两个阶段：先把每批排好，再把小文件并起来

外排序基本就两段，第一段叫排序段，把大文件按内存装得下的量切成一批一批，每批读进来用内排序排好，写成一个小文件，这些小文件内部都是有序的；第二段叫归并段，把这些小文件两两归并，每并一次文件数目减半、单个文件变大，直到只剩一个文件，它就是全局有序的结果。

这两段的分工很干净：排序段只负责把数据变成一小段一小段有序，归并段只负责把有序段拼起来。前者用的是前面写过的那种内排序，后者用的是第一节那个合并动作。数据大了之后真正花时间的是磁盘读写，所以整个设计的重点是把随机读写换成顺序读写。

接下来几节拿一千万条整数做例子，从造数据开始一路做到结果落盘。一千万条占 39MB，内存装得下，拿它做演示是为了让整个过程跑得完；真到数据比内存大的时候，流程一模一样，只是每批的条数要按可用内存重新算。

七、一千万条整数测试

演示用的数据是随机整数，直接落成二进制。原因有两个：一是 4 字节一条，一千万条正好 39MB 上下，换成十进制文本每条要 10 个字符上下，文件变成 100MB 还多；二是二进制整块读写就行，文本还得逐条解析，这个解析开销在读写一千万条的时候会盖过排序本身。

#defineBLOCK65536/* 一块 256KB，读写都按这个单位来 */staticvoidCreateData(constchar*path,longtotal){FILE*f=fopen(path,"wb");int*buf=(int*)malloc(sizeof(int)*BLOCK);longleft=total;srand(20261019);while(left>0){inti;intn=(left>BLOCK)?BLOCK:(int)left;for(i=0;i<n;i++){buf[i]=rand();}fwrite(buf,sizeof(int),n,f);left-=n;}fclose(f);free(buf);}

这块数据在这台机器上一次跑完是 73.434 毫秒，文件 39MB 左右，跟 4 字节乘以一千万对得上。读写都按 256KB 一块来，是因为磁盘和文件系统喜欢成块的顺序读写，一次读写一个字节跟一次读写一块，调用次数的差距是几万倍。

有了大文件，第一段就开始切，每批读 10 万条出来用 qsort 排好，写成 run_0000.bin、run_0001.bin 这样的小文件，读完整个大文件就得到一批内部有序的小文件。一批 10 万条约 400KB，读进来排好的时间跟前面内排序那一组数据对得上，十万条归并 8.948 毫秒、qsort 10.514 毫秒。

图 7 一千万条整数：39MB 的文件切成一百块

staticintSplitToRuns(constchar*src,intbatch,charnames[][64]){FILE*in=fopen(src,"rb");int*buf=(int*)malloc(sizeof(int)*batch);intcnt=0;for(;;){intgot=(int)fread(buf,sizeof(int),batch,in);FILE*out;if(got<=0){break;}qsort(buf,got,sizeof(int),CmpInt);sprintf(names[cnt],"run_%04d.bin",cnt);out=fopen(names[cnt],"wb");fwrite(buf,sizeof(int),got,out);fclose(out);cnt++;}fclose(in);free(buf);returncnt;}

一千万条按每批 10 万条切，得到 100 个小文件。这一步实测 1101.213 毫秒，其中包含读、排、写三件事。拿前面的数字对一下：十万条 qsort 10.514 毫秒乘以 100 批，光排序就要 1051 毫秒，剩下的几十毫秒是读写，说明这一步的时间基本被排序占满，IO 反而不是瓶颈。

第二段要把两个有序小文件并成一个，如果每读一条数据就调一次 fread 读 4 个字节，一千万条数据跑一趟就是一千万次库函数调用，光调用开销就能把时间翻几倍；所以这里给每个文件配一块 256KB 的缓冲，一次读满一块，程序内部慢慢消费，写出去的也一样先攒一块再落盘。

typedefstruct{FILE*f;intbuf[BLOCK];intpos;intcnt;}Reader;typedefstruct{FILE*f;intbuf[BLOCK];intpos;}Writer;staticintReaderNext(Reader*r,int*out){if(r->pos>=r->cnt){r->cnt=(int)fread(r->buf,sizeof(int),BLOCK,r->f);r->pos=0;if(r->cnt<=0){return0;}}*out=r->buf[r->pos++];return1;}staticlongMergeTwo(constchar*f1,constchar*f2,constchar*out){Reader r1,r2;Writer w;inta,b;inthasA,hasB;longwritten=0;/* 打开两个输入与一个输出，缓冲置零，细节省略 */InitReader(&r1,f1);InitReader(&r2,f2);InitWriter(&w,out);hasA=ReaderNext(&r1,&a);hasB=ReaderNext(&r2,&b);while(hasA&&hasB){if(a<=b){WriterPut(&w,a);hasA=ReaderNext(&r1,&a);}else{WriterPut(&w,b);hasB=ReaderNext(&r2,&b);}written++;}while(hasA){WriterPut(&w,a);written++;hasA=ReaderNext(&r1,&a);}while(hasB){WriterPut(&w,b);written++;hasB=ReaderNext(&r2,&b);}/* 收尾：冲掉缓冲，关三个文件 */FinishWriter(&w);returnwritten;}

代码里的 InitReader 与 FinishWriter 是打开文件、把 pos 与 cnt 清零、最后冲缓冲的几个助手函数，为了篇幅没展开。合并的主循环跟第一节那个动作一样，只是数据的来路从内存里的两个下标变成了两个文件，比较仍然是 a 小于等于 b 就取 a，稳定性的道理在文件上也成立。

这里用的是双路归并，每趟只并两个文件。想一趟并 k 个文件也可以，代价是要在 k 个队头里挑最小的，简单扫一遍是 k，用堆可以做到 log k，具体做法在第十篇的堆里写过。双路的好处是每个文件只需要一块缓冲，内存占用小，实现也简单，代价是趟数多一点。

批大小是这个流程里唯一要调的参数，批取大，切出来的小文件少，归并的趟数就少，第二段的 IO 总量跟着降；批取大也意味着一次性要占更多内存，一千万条、每批一百万条就是 4MB 的缓冲。批取小，内存占用低，但小文件数目翻倍，趟数和 IO 总量都要涨。

图 8 批大省钱在归并，批小省钱在排序，总数差得不多

两档批大小都跑了一遍，数字摆在一起看：

批取一百万条的时候，分批排序慢了 200 毫秒出头，归并快了一半，总账反而少了 100 多毫秒。分批排序变慢的原因是每一批的规模大了十倍，qsort 在百万条上要做更多的缓存换入换出；归并变快的原因很直白，块数从 100 降到 10，趟数从 7 降到 4，来回复制整个 39MB 的次数少了三趟。

批再大下去会顶到内存上限，批小到几万条又会把趟数堆上来。真正能定这个参数的是可用内存：批大小的四倍字节数加上几个 256KB 的缓冲区，必须稳稳落在可用内存以内，剩下的一段留给别的程序。数据量大到连一批都放不下的时候，外排序就没有意义了，只能换成按位分段的那种做法。

归并段是一个循环：把当前所有文件两两合并，合并出来的新文件顶替原来的两个，文件数目大致减半；个数是奇数的时候最后那个直接改名搬过去，下一趟继续参与。一直做到只剩一个文件，它就是有序结果。

图 9 文件个数每趟减半，减到只剩一个就完事

staticintOnePass(charnames[][64],intcnt,intpass){staticcharnext[128][64];inti,n=0;for(i=0;i<cnt;i+=2){if(i+1<cnt){sprintf(next[n],"m_%d_%04d.bin",pass,n);MergeTwo(names[i],names[i+1],next[n]);remove(names[i]);remove(names[i+1]);}else{sprintf(next[n],"m_%d_%04d.bin",pass,n);CopyFile(names[i],next[n]);remove(names[i]);}n++;}for(i=0;i<n;i++){strcpy(names[i],next[i]);}returnn;}

每趟并完立刻删掉两个输入文件，这是流程里必须的一步。不删的话，一趟下来磁盘上同时留着新旧两批文件，占用翻倍，一百块小文件跑七趟能堆出好几百个文件。

一千万条、每批十万条这一档跑下来，文件个数是这样一路减下去的：100 变成 50，再变成 25，25 是奇数、最后一组分不掉就搬到下一趟，于是变成 13，接着 7、4、2，最后剩 1。整个过程 7 趟，连切分带归并一共造了 202 个临时文件，最后那个文件改名成结果，结果 1000 万条。

结果没有靠肉眼抽查，办法是把原始文件读进内存用 qsort 排一遍，再跟外排序的结果逐条比对，一千万条比完完全一致。两档批大小都这样比过，结果都一致，没有一条对不上。

八、内外排序的分界

两段流程跑完，回头看一个容易含糊的问题：什么时候该用外排序。分界的标准是同时要待在内存里的那部分占多少，光看数据量本身说明不了问题。一千万条整数只有 39MB，随便哪台机器都装得下，内排序完全能处理；换成十亿条就是 4GB 上下，这时候才轮到外排序。内排序要求整份数据在内存里，外排序只要求一批数据加上几个缓冲区在内存里，剩下的都存在磁盘上。

把测到的数字汇总成两张表，内排序这张看的是内存里的表现：

外排序这张看的是磁盘上的表现，两档批大小：

升序数据那一行值得多说一句，别家的排序碰到已经有序的数据会快很多，冒泡一趟就退出来了，插入排序只要 N 减一次比较；归并排序不管数据长什么样都要走完整个递归树，每一层都要把元素从原数组抄进临时数组再抄回来。实测里升序一百万条确实比随机快，从 106.565 毫秒降到 26.944 毫秒，快的原因是分支预测与缓存命中变好，而不是比较次数变少。

最后用 valgrind 把测试程序跑了一遍，2203 次申请、2203 次释放，263428 字节，没有一块内存留在外面，错误报告是零。归并的两处动态内存就是临时数组，递归版与非递归版各申请一次、各释放一次，这个数量对得上。

踩坑点

• 临时数组不能申请在合并函数里面。合并一共发生 N 减一次，每次都申请再释放，一百万条就是上百万次 malloc 与 free，调用本身要花时间，更要命的是每次都拿到刚释放的内存，缓存全部失效；临时数组应该在排序入口申请一次，作为参数一路传下去。
• 非递归版的下标边界要判断两次，顺序还不能反。数组长度不是二的幂时最后一组凑不齐，mid 越过末尾说明右段整个不存在，right 越过末尾说明右段短了一截；先判断 mid 再夹 right，反过来会拿着一组不存在的下标去合并。
• 比较写成严格小于会丢掉稳定性。合并时左边队头小于等于右边队头才取左边，等号这一边给左段，相等记录的先后才保得住；改成严格小于，相等时取右边，稳定性立刻没了。这个错误在纯整数上看不出来，要用带编号的记录跑一遍。
• 数据用文本格式存，读写成本会比想象中大。一千万条文本要 100MB 上下，每条还要逐条解析，格式化输入输出比整块二进制慢一个量级；演示里用文本是为了方便看，真正搬运大量数据时二进制加固定长度更合适。
• 一次只读一条数据会让函数调用变成瓶颈。用 fread 按四个字节读，一千万条就是上千万次调用，每次都有参数检查与锁的开销，加起来比读写本身还贵；给每个文件配一块几万条的缓冲，调用次数压到几百次，这项开销就没了。
• 中间文件用完要立刻删。每趟并完不删输入，磁盘占用翻倍，目录里堆着几百个文件，跑到一半磁盘满了才发现；合并成功之后删掉两个输入，删除失败也要看返回值。
• 归并完的小文件要改名顶替输入文件。循环归并的写法是读两个小文件、写一个临时文件、删掉两个输入、再把临时文件改成第一个输入的名字；漏掉改名这一步，下一轮读的还是旧数据，循环不会正常收敛。
• 批大小要按可用内存定，不能只看单批排序快不快。批取得大，切出来的文件少、归并趟数少、IO 总量低，代价是一次性占更多内存；批取得小，内存占用低，文件数目与趟数都涨。实测两档批大小的总耗时差一百多毫秒，差距不大，参数主要还是看内存。

本篇总结（模拟面试问题）

问：归并排序为什么是 N log N，跟快排的 N log N 有什么不同？

核心要点：递归树高 log2 N，每一层所有区间的长度加起来还是 N，每层的合并总代价是 N，相乘就是 N log N。差别在代价花的地方：快排花在划分时的比较与交换上，归并花在把元素抄进临时数组再抄回来上，同样数量级下归并的常数项跟搬动次数直接挂钩。

问：归并排序的稳定性从哪来，改哪个符号会破坏它？

核心要点：从合并时的比较符号来，左边队头小于等于右边队头就取左边，相等时左边先出，相等记录原来的先后就保住了；把小于等于改成严格小于，相等时改成取右边，稳定性立刻丢失，而纯整数上看不出区别。

问：归并排序为什么需要 O(N) 的额外空间，能不能省掉？

核心要点：合并两个相邻有序段时，结果要写回原位置，而那里还存着没搬走的数据，必须有一块地方暂存。省掉的办法有两种：换成链表这种节点可以重连的结构，额外空间降到常数；或者用原地归并，代价是元素搬动次数大幅上升，实测比带临时数组慢。

问：两个有序段合并，比较次数最多是多少？

核心要点：最多 N 减一次，N 是两段加起来的总长度。每比较一次至少搬走一个元素，搬走 N 减一个之后只剩一段连着的尾部，直接接上就完事，这也是每一层的代价能精确写成 N 的原因。

问：非递归归并要小心哪些边界？

核心要点：mid 越过末尾说明剩下的连左段都不够，这一轮跳过；right 越过末尾说明右段短了，夹到 n 减一；两处顺序不能反。另外段长翻倍要写成乘二，写成加二会让趟数退化成 N，总代价变成 N 的平方。

问：外排序为什么分两个阶段，各解决什么问题？

核心要点：排序段把放不进内存的大文件切成一批批，每批用内排序排好写成小文件，解决的是单批内部的顺序；归并段把小文件两两合并，解决的是跨批的顺序，趟数是对数级的。两段合起来，磁盘上的数据也能得到全局有序的结果。

问：外排序里批大小取大取小分别换来什么？

核心要点：批取得大，切出来的文件少、归并趟数少、IO 总量低，代价是一次性占用更多内存，单批排序也变长；批取得小，内存占用低，文件数目与趟数都涨，IO 总量跟着涨。实测两档批大小总耗时差一百多毫秒，差距不大，选参数主要看可用内存。

问：同样的归并思路能不能用在链表上？

核心要点：能，而且链表上做归并比数组更省空间。链表合并只改 next 指针，不需要临时数组，额外空间是常数；找中间节点用快慢指针，切两半是一步指针操作。这样写出来的排序是链表上少有的稳定且 O(N log N) 的做法。

参考

• 合并两个有序数组（LeetCode 88）
• 排序数组（LeetCode 912）
• 排序链表（LeetCode 148）
• 合并 K 个升序链表（LeetCode 23）
• External sorting（维基百科）
• GNU coreutils 的 sort 手册
• Big-O Cheat Sheet