说到排序，大家第一反应基本上是内排序，是的，算法嘛，玩的就是内存，然而内存是有限制的，总有装不下的那一天，此时就可以来玩玩外排序，当然在我看来，外排序考验的是一个程序员的架构能力，而不仅仅局限于排序这个层次。
一：N路归并排序1.概序我们知道算法中有一种叫做分治思想，一个大问题我们可以采取分而治之，各个突破，当子问题解决了，大问题也就KO了，还有一点我们知道内排序的归并排序是采用二路归并的，因为分治后有LogN层，每层两路归并需要N的时候，最后复杂度为NlogN，那么外排序我们可以将这个“二”扩大到M，也就是将一个大文件分成M个小文件，每个小文件是有序的，然后对应在内存中我们开M个优先队列，每个队列从对应编号的文件中读取TopN条记录，然后我们从M路队列中各取一个数字进入中转站队列，并将该数字打上队列编号标记，当从中转站出来的最小数字就是我们最后要排序的数字之一，因为该数字打上了队列编号，所以方便我们通知对应的编号队列继续出数字进入中转站队列，可以看出中转站一直保存了M个记录，当中转站中的所有数字都出队完毕，则外排序结束。如果大家有点蒙的话，我再配合一张图，相信大家就会一目了然，这考验的是我们的架构能力。
图中这里有个Batch容器，这个容器我是基于性能考虑的，当batch=n时，我们定时刷新到文件中，保证内存有足够的空间。
2.构建1)生成数据这个基本没什么好说的，采用随机数生成n条记录。
#region随机生成数据///summary///随机生成数据///paramname="max"执行生成的数据上线/param////summarypublicstaticvoidCreateData(intmax){varsw=newStreamWriter(Environment.CurrentDirectory+"//demo.txt");for(inti=0;imax;i++){Thread.Sleep(2);varrand=newRandom((int)DateTime.Now.Ticks).Next(0,int.MaxValue3);sw.WriteLine(rand);}sw.Close();}#endregion2)切分数据
根据实际情况我们来决定到底要分成多少个小文件，并且小文件的数据必须是有序的，小文件的个数也对应这内存中有多少个优先队列。
#region将数据进行分份///summary///将数据进行分份///paramname="size"每页要显示的条数/param////summarypublicstaticintSplit(intsize){//文件总记录数inttotalCount=0;//每一份文件存放size条记录Listintsmall=newListint();varsr=newStreamReader((Environment.CurrentDirectory+"//demo.txt"));varpageSize=size;intpageCount=0;intpageIndex=0;while(true){varline=sr.ReadLine();if(!string.IsNullOrEmpty(line)){totalCount++;//加入小集合中small.Add(Convert.ToInt32(line));//说明已经到达指定的size条数了if(totalCount%pageSize==0){pageIndex=totalCount/pageSize;small=small.OrderBy(i=i).Select(i=i).ToList();File.WriteAllLines(Environment.CurrentDirectory+"//"+pageIndex+".txt",small.Select(i=i.ToString()));small.Clear();}}else{//说明已经读完了，将剩余的small记录写入到文件中pageCount=(int)Math.Ceiling((double)totalCount/pageSize);small=small.OrderBy(i=i).Select(i=i).ToList();File.WriteAllLines(Environment.CurrentDirectory+"//"+pageCount+".txt",small.Select(i=i.ToString()));break;}}returnpageCount;}#endregion3)加入队列
我们知道内存队列存放的只是小文件的topN条记录，当内存队列为空时，我们需要再次从小文件中读取下一批的TopN条数据，然后放入中转站继续进行比较。
#region将数据加入指定编号队列///summary///将数据加入指定编号队列////summary///paramname="i"队列编号/param///paramname="skip"文件中跳过的条数/param///paramname="list"/param///paramname="top"需要每次读取的条数/parampublicstaticvoidAddQueue(inti,ListPriorityQueueint?list,refint[]skip,inttop=){varresult=File.ReadAllLines((Environment.CurrentDirectory+"//"+(i+1)+".txt")).Skip(skip).Take(top).Select(j=Convert.ToInt32(j));//加入到集合中foreach(variteminresult)list.Eequeue(null,item);//将个数累计到skip中，表示下次要跳过的记录数skip+=result.Count();}#endregion4)测试
最后我们来测试一下:
数据量：short.MaxValue。
内存存放量：。
在这种场景下，我们决定每个文件放0条，也就有33个小文件，也就有33个内存队列，每个队列取Top条，Batch=时刷新硬盘，中转站存放个数字（因为入中转站时打上了队列标记）,最后内存活动最大总数为：sum=33++66=896。
时间复杂度为N*logN。当然这个“阀值”，我们可以再仔细微调。
publicstaticvoidMain(){//生成2^15数据CreateData(short.MaxValue);//每个文件存放0条varpageSize=0;//达到batchCount就刷新记录varbatchCount=0;//判断需要开启的队列varpageCount=Split(pageSize);//内存限制：1条ListPriorityQueueint?list=newListPriorityQueueint?();//定义一个队列中转器PriorityQueueint?queueControl=newPriorityQueueint?();//定义每个队列完成状态bool[]