【数据结构】归并与外排序 H.莓飛 个人主页❄️个人专栏「C」「数据结构」「Linux系统编程」✨ 心不畏死踏屍前行。 代码仓库cocatrice_csdn_code 博主简介概览递归与非递归两种归并写法临时数组与它的空间代价相等取左边内外分界如何决定核心知识一、简述前面十几篇里排序的动作要么是拿一个元素往回找位置要么是在区间里来回换都比对过元素之间的大小关系。归并换了个角度它先假设手上已经有两段排好序的数据只负责把这两段拼成一段。拼的过程非常朴素两段各放一个游标在队头每次比较两个队头的值小的那个搬进结果游标往后走一格直到某一段搬空剩下的那一段直接整体接上去。拿 1 4 7 和 2 3 9 走一遍先比 1 和 2 取 1再比 4 和 2 取 2接着比 4 和 3 取 3然后 4 比 9 取 47 比 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){intileft;intjmid1;intkleft;while(imidjright){if(a[i]a[j])/* 相等时先取左边稳定性就靠这个等号 */{tmp[k]a[i];}else{tmp[k]a[j];}}while(imid){tmp[k]a[i];}while(jright){tmp[k]a[j];}memcpy(aleft,tmpleft,sizeof(int)*(right-left1));}临时数组申请在递归外面这一步值得单独说一句。合并的次数是 N 减一次如果每合一回都去 malloc 一次 4MB一百万条数据要走上百万次申请与释放光是申请这块内存就够把整个排序拖成几秒申请一次反复用这一项开销就摊成了常数。intMergeSort(int*a,intn){int*tmp;if(aNULL||n2){return0;}tmp(int*)malloc(sizeof(int)*n);if(tmpNULL){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(gap1;gapn;gap*2){inti;for(i0;in;i2*gap){intlefti;intmidigap-1;intrighti2*gap-1;if(midn)/* 剩下的连左段都没凑满这一轮不用并 */{break;}if(rightn){rightn-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 2b3a 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*ffopen(path,wb);int*buf(int*)malloc(sizeof(int)*BLOCK);longlefttotal;srand(20261019);while(left0){inti;intn(leftBLOCK)?BLOCK:(int)left;for(i0;in;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*infopen(src,rb);int*buf(int*)malloc(sizeof(int)*batch);intcnt0;for(;;){intgot(int)fread(buf,sizeof(int),batch,in);FILE*out;if(got0){break;}qsort(buf,got,sizeof(int),CmpInt);sprintf(names[cnt],run_%04d.bin,cnt);outfopen(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-posr-cnt){r-cnt(int)fread(r-buf,sizeof(int),BLOCK,r-f);r-pos0;if(r-cnt0){return0;}}*outr-buf[r-pos];return1;}staticlongMergeTwo(constchar*f1,constchar*f2,constchar*out){Reader r1,r2;Writer w;inta,b;inthasA,hasB;longwritten0;/* 打开两个输入与一个输出缓冲置零细节省略 */InitReader(r1,f1);InitReader(r2,f2);InitWriter(w,out);hasAReaderNext(r1,a);hasBReaderNext(r2,b);while(hasAhasB){if(ab){WriterPut(w,a);hasAReaderNext(r1,a);}else{WriterPut(w,b);hasBReaderNext(r2,b);}written;}while(hasA){WriterPut(w,a);written;hasAReaderNext(r1,a);}while(hasB){WriterPut(w,b);written;hasBReaderNext(r2,b);}/* 收尾冲掉缓冲关三个文件 */FinishWriter(w);returnwritten;}代码里的 InitReader 与 FinishWriter 是打开文件、把 pos 与 cnt 清零、最后冲缓冲的几个助手函数为了篇幅没展开。合并的主循环跟第一节那个动作一样只是数据的来路从内存里的两个下标变成了两个文件比较仍然是 a 小于等于 b 就取 a稳定性的道理在文件上也成立。这里用的是双路归并每趟只并两个文件。想一趟并 k 个文件也可以代价是要在 k 个队头里挑最小的简单扫一遍是 k用堆可以做到 log k具体做法在第十篇的堆里写过。双路的好处是每个文件只需要一块缓冲内存占用小实现也简单代价是趟数多一点。批大小是这个流程里唯一要调的参数批取大切出来的小文件少归并的趟数就少第二段的 IO 总量跟着降批取大也意味着一次性要占更多内存一千万条、每批一百万条就是 4MB 的缓冲。批取小内存占用低但小文件数目翻倍趟数和 IO 总量都要涨。图 8 批大省钱在归并批小省钱在排序总数差得不多两档批大小都跑了一遍数字摆在一起看批大小切出块数分批排序归并趟数循环归并临时文件总耗时十万条1001101.213 毫秒7691.123 毫秒202 个1792.336 毫秒一百万条101322.620 毫秒4360.975 毫秒21 个1683.595 毫秒批取一百万条的时候分批排序慢了 200 毫秒出头归并快了一半总账反而少了 100 多毫秒。分批排序变慢的原因是每一批的规模大了十倍qsort 在百万条上要做更多的缓存换入换出归并变快的原因很直白块数从 100 降到 10趟数从 7 降到 4来回复制整个 39MB 的次数少了三趟。批再大下去会顶到内存上限批小到几万条又会把趟数堆上来。真正能定这个参数的是可用内存批大小的四倍字节数加上几个 256KB 的缓冲区必须稳稳落在可用内存以内剩下的一段留给别的程序。数据量大到连一批都放不下的时候外排序就没有意义了只能换成按位分段的那种做法。归并段是一个循环把当前所有文件两两合并合并出来的新文件顶替原来的两个文件数目大致减半个数是奇数的时候最后那个直接改名搬过去下一趟继续参与。一直做到只剩一个文件它就是有序结果。图 9 文件个数每趟减半减到只剩一个就完事staticintOnePass(charnames[][64],intcnt,intpass){staticcharnext[128][64];inti,n0;for(i0;icnt;i2){if(i1cnt){sprintf(next[n],m_%d_%04d.bin,pass,n);MergeTwo(names[i],names[i1],next[n]);remove(names[i]);remove(names[i1]);}else{sprintf(next[n],m_%d_%04d.bin,pass,n);CopyFile(names[i],next[n]);remove(names[i]);}n;}for(i0;in;i){strcpy(names[i],next[i]);}returnn;}每趟并完立刻删掉两个输入文件这是流程里必须的一步。不删的话一趟下来磁盘上同时留着新旧两批文件占用翻倍一百块小文件跑七趟能堆出好几百个文件。一千万条、每批十万条这一档跑下来文件个数是这样一路减下去的100 变成 50再变成 2525 是奇数、最后一组分不掉就搬到下一趟于是变成 13接着 7、4、2最后剩 1。整个过程 7 趟连切分带归并一共造了 202 个临时文件最后那个文件改名成结果结果 1000 万条。结果没有靠肉眼抽查办法是把原始文件读进内存用 qsort 排一遍再跟外排序的结果逐条比对一千万条比完完全一致。两档批大小都这样比过结果都一致没有一条对不上。八、内外排序的分界两段流程跑完回头看一个容易含糊的问题什么时候该用外排序。分界的标准是同时要待在内存里的那部分占多少光看数据量本身说明不了问题。一千万条整数只有 39MB随便哪台机器都装得下内排序完全能处理换成十亿条就是 4GB 上下这时候才轮到外排序。内排序要求整份数据在内存里外排序只要求一批数据加上几个缓冲区在内存里剩下的都存在磁盘上。把测到的数字汇总成两张表内排序这张看的是内存里的表现数据递归归并非递归归并qsort十万条随机8.948 毫秒8.207 毫秒10.514 毫秒一百万条随机106.565 毫秒99.266 毫秒126.475 毫秒一百万条升序26.944 毫秒24.101 毫秒未测外排序这张看的是磁盘上的表现两档批大小项目每批十万条每批一百万条切出小文件100 个10 个归并趟数7 趟4 趟临时文件总数202 个21 个总耗时1792.336 毫秒1683.595 毫秒结果条数1000000010000000升序数据那一行值得多说一句别家的排序碰到已经有序的数据会快很多冒泡一趟就退出来了插入排序只要 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 23External sorting维基百科GNU coreutils 的 sort 手册Big-O Cheat Sheet 
长河君 · 2026/10/26 1:57:19 · 阅读 1.2k 【数据结构】归并与外排序
【数据结构】归并与外排序 H.莓飛 个人主页❄️个人专栏「C」「数据结构」「Linux系统编程」✨ 心不畏死踏屍前行。 代码仓库cocatrice_csdn_code 博主简介概览递归与非递归两种归并写法临时数组与它的空间代价相等取左边内外分界如何决定核心知识一、简述前面十几篇里排序的动作要么是拿一个元素往回找位置要么是在区间里来回换都比对过元素之间的大小关系。归并换了个角度它先假设手上已经有两段排好序的数据只负责把这两段拼成一段。拼的过程非常朴素两段各放一个游标在队头每次比较两个队头的值小的那个搬进结果游标往后走一格直到某一段搬空剩下的那一段直接整体接上去。拿 1 4 7 和 2 3 9 走一遍先比 1 和 2 取 1再比 4 和 2 取 2接着比 4 和 3 取 3然后 4 比 9 取 47 比 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){intileft;intjmid1;intkleft;while(imidjright){if(a[i]a[j])/* 相等时先取左边稳定性就靠这个等号 */{tmp[k]a[i];}else{tmp[k]a[j];}}while(imid){tmp[k]a[i];}while(jright){tmp[k]a[j];}memcpy(aleft,tmpleft,sizeof(int)*(right-left1));}临时数组申请在递归外面这一步值得单独说一句。合并的次数是 N 减一次如果每合一回都去 malloc 一次 4MB一百万条数据要走上百万次申请与释放光是申请这块内存就够把整个排序拖成几秒申请一次反复用这一项开销就摊成了常数。intMergeSort(int*a,intn){int*tmp;if(aNULL||n2){return0;}tmp(int*)malloc(sizeof(int)*n);if(tmpNULL){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(gap1;gapn;gap*2){inti;for(i0;in;i2*gap){intlefti;intmidigap-1;intrighti2*gap-1;if(midn)/* 剩下的连左段都没凑满这一轮不用并 */{break;}if(rightn){rightn-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 2b3a 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*ffopen(path,wb);int*buf(int*)malloc(sizeof(int)*BLOCK);longlefttotal;srand(20261019);while(left0){inti;intn(leftBLOCK)?BLOCK:(int)left;for(i0;in;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*infopen(src,rb);int*buf(int*)malloc(sizeof(int)*batch);intcnt0;for(;;){intgot(int)fread(buf,sizeof(int),batch,in);FILE*out;if(got0){break;}qsort(buf,got,sizeof(int),CmpInt);sprintf(names[cnt],run_%04d.bin,cnt);outfopen(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-posr-cnt){r-cnt(int)fread(r-buf,sizeof(int),BLOCK,r-f);r-pos0;if(r-cnt0){return0;}}*outr-buf[r-pos];return1;}staticlongMergeTwo(constchar*f1,constchar*f2,constchar*out){Reader r1,r2;Writer w;inta,b;inthasA,hasB;longwritten0;/* 打开两个输入与一个输出缓冲置零细节省略 */InitReader(r1,f1);InitReader(r2,f2);InitWriter(w,out);hasAReaderNext(r1,a);hasBReaderNext(r2,b);while(hasAhasB){if(ab){WriterPut(w,a);hasAReaderNext(r1,a);}else{WriterPut(w,b);hasBReaderNext(r2,b);}written;}while(hasA){WriterPut(w,a);written;hasAReaderNext(r1,a);}while(hasB){WriterPut(w,b);written;hasBReaderNext(r2,b);}/* 收尾冲掉缓冲关三个文件 */FinishWriter(w);returnwritten;}代码里的 InitReader 与 FinishWriter 是打开文件、把 pos 与 cnt 清零、最后冲缓冲的几个助手函数为了篇幅没展开。合并的主循环跟第一节那个动作一样只是数据的来路从内存里的两个下标变成了两个文件比较仍然是 a 小于等于 b 就取 a稳定性的道理在文件上也成立。这里用的是双路归并每趟只并两个文件。想一趟并 k 个文件也可以代价是要在 k 个队头里挑最小的简单扫一遍是 k用堆可以做到 log k具体做法在第十篇的堆里写过。双路的好处是每个文件只需要一块缓冲内存占用小实现也简单代价是趟数多一点。批大小是这个流程里唯一要调的参数批取大切出来的小文件少归并的趟数就少第二段的 IO 总量跟着降批取大也意味着一次性要占更多内存一千万条、每批一百万条就是 4MB 的缓冲。批取小内存占用低但小文件数目翻倍趟数和 IO 总量都要涨。图 8 批大省钱在归并批小省钱在排序总数差得不多两档批大小都跑了一遍数字摆在一起看批大小切出块数分批排序归并趟数循环归并临时文件总耗时十万条1001101.213 毫秒7691.123 毫秒202 个1792.336 毫秒一百万条101322.620 毫秒4360.975 毫秒21 个1683.595 毫秒批取一百万条的时候分批排序慢了 200 毫秒出头归并快了一半总账反而少了 100 多毫秒。分批排序变慢的原因是每一批的规模大了十倍qsort 在百万条上要做更多的缓存换入换出归并变快的原因很直白块数从 100 降到 10趟数从 7 降到 4来回复制整个 39MB 的次数少了三趟。批再大下去会顶到内存上限批小到几万条又会把趟数堆上来。真正能定这个参数的是可用内存批大小的四倍字节数加上几个 256KB 的缓冲区必须稳稳落在可用内存以内剩下的一段留给别的程序。数据量大到连一批都放不下的时候外排序就没有意义了只能换成按位分段的那种做法。归并段是一个循环把当前所有文件两两合并合并出来的新文件顶替原来的两个文件数目大致减半个数是奇数的时候最后那个直接改名搬过去下一趟继续参与。一直做到只剩一个文件它就是有序结果。图 9 文件个数每趟减半减到只剩一个就完事staticintOnePass(charnames[][64],intcnt,intpass){staticcharnext[128][64];inti,n0;for(i0;icnt;i2){if(i1cnt){sprintf(next[n],m_%d_%04d.bin,pass,n);MergeTwo(names[i],names[i1],next[n]);remove(names[i]);remove(names[i1]);}else{sprintf(next[n],m_%d_%04d.bin,pass,n);CopyFile(names[i],next[n]);remove(names[i]);}n;}for(i0;in;i){strcpy(names[i],next[i]);}returnn;}每趟并完立刻删掉两个输入文件这是流程里必须的一步。不删的话一趟下来磁盘上同时留着新旧两批文件占用翻倍一百块小文件跑七趟能堆出好几百个文件。一千万条、每批十万条这一档跑下来文件个数是这样一路减下去的100 变成 50再变成 2525 是奇数、最后一组分不掉就搬到下一趟于是变成 13接着 7、4、2最后剩 1。整个过程 7 趟连切分带归并一共造了 202 个临时文件最后那个文件改名成结果结果 1000 万条。结果没有靠肉眼抽查办法是把原始文件读进内存用 qsort 排一遍再跟外排序的结果逐条比对一千万条比完完全一致。两档批大小都这样比过结果都一致没有一条对不上。八、内外排序的分界两段流程跑完回头看一个容易含糊的问题什么时候该用外排序。分界的标准是同时要待在内存里的那部分占多少光看数据量本身说明不了问题。一千万条整数只有 39MB随便哪台机器都装得下内排序完全能处理换成十亿条就是 4GB 上下这时候才轮到外排序。内排序要求整份数据在内存里外排序只要求一批数据加上几个缓冲区在内存里剩下的都存在磁盘上。把测到的数字汇总成两张表内排序这张看的是内存里的表现数据递归归并非递归归并qsort十万条随机8.948 毫秒8.207 毫秒10.514 毫秒一百万条随机106.565 毫秒99.266 毫秒126.475 毫秒一百万条升序26.944 毫秒24.101 毫秒未测外排序这张看的是磁盘上的表现两档批大小项目每批十万条每批一百万条切出小文件100 个10 个归并趟数7 趟4 趟临时文件总数202 个21 个总耗时1792.336 毫秒1683.595 毫秒结果条数1000000010000000升序数据那一行值得多说一句别家的排序碰到已经有序的数据会快很多冒泡一趟就退出来了插入排序只要 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 23External sorting维基百科GNU coreutils 的 sort 手册Big-O Cheat Sheet