什么是外排序？
外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存。（摘自百度）
再简单点来说。比如我们要对10亿个数进行排序。如果用int[]来存储这10亿个数的话，我们需要3*1000000000/8/1024/1024/1024≈3.7G。对于只有2G内存的电脑来说根本就跑不起来。所以这时候什么内存排序算法都玩不起来了。
外排序的思想是将这10亿条数据分割成N个小项（比如每个分割项放2000条数据，然后对这2000条数据进行排序[2000个int放入内存当中只需要7.8K]，排序后写入一个txt文件中）。这样就能得到N个有序的小项。再把这些小项通过运算聚合起来，得到最终结果。说白了其实就跟归并排序思路相似。
拿实际生活举例，比如我们想知道一个图书馆有多少本书，你会怎样做？自己一个一口气肯定数不完。只能今天数一个区域，得到一个总数。明天数另外一个区域得到一个总数。最后把所有总数聚集起来。又或者将图书馆分成N个区域，然后找N个人来数这N个区域。他们数完后向你汇报，你再把他们汇报的结果聚集起来得到最终结果。这跟google提出的MapReduce思想相似。跟之前一个人数的区别只在于一个是单线程，一个是多线程。
知道了思路之后，我们实现起来也就非常简单了
static void Main(string[] args) { int count = 11;//生成数据的数量 int step = 2;//设置分割时每份多少条 var sourcepath = string.Format("{0}{1}.txt", AppDomain.CurrentDomain.BaseDirectory, "source"); Init(sourcepath, count);//初始化数据--把所有数据写入source.txt的文件中 Queue<string> queue = Skip(sourcepath, step);//分割source.txt文件，并将每份都进行排序。所以分割后的每个文件中的内容都是有序的 while (queue.Count > 1)//把有序的队列聚合在一起 { Sort(queue); } System.Diagnostics.Process.Start(queue.First());//显示结果 } /// <summary> /// 初始化数据 /// </summary> /// <param name="sourcepath"></param> /// <param name="count"></param> private static void Init(string sourcepath, int count) { using (StreamWriter writer = new StreamWriter(sourcepath, false)) { Random random = new Random(); for (int i = 0; i < count; i++) { writer.WriteLine(random.Next(1000)); } writer.Close(); } } /// <summary> /// 对源数据进行分割 /// </summary> /// <param name="sourcepath"></param> /// <param name="step"></param> /// <returns></returns> private static Queue<string> Skip(string sourcepath, int step) { Queue<string> queue = new Queue<string>(); StreamReader read = new StreamReader(sourcepath); while (true) { List<long> temp = new List<long>(); for (int i = 0; i < step; i++) { string value = read.ReadLine(); if (string.IsNullOrEmpty(value)) break; temp.Add(long.Parse(value)); } if (temp.Count == 0) break; string tempfile = null; do { tempfile = string.Format("{0}{1}.txt", AppDomain.CurrentDomain.BaseDirectory, DateTime.Now.ToString("MMddHHmmssfff")); } while (File.Exists(tempfile)); StreamWriter writer = new StreamWriter(tempfile); temp = temp.OrderBy(x => x).ToList(); temp.ForEach(x => writer.WriteLine(x)); queue.Enqueue(tempfile); writer.Close(); writer.Dispose(); } read.Close(); read.Dispose(); return queue; } private static void Sort(Queue<string> queue) { StreamReader read1 = new StreamReader(queue.Dequeue()); StreamReader read2 = new StreamReader(queue.Dequeue()); Func<StreamReader, long?> GetValue = (x) => { string temp = x.ReadLine(); if (temp == null) return null; return long.Parse(temp); }; long? value1 = GetValue(read1); long? value2 = GetValue(read2); string resultpath = null; do { resultpath = string.Format("{0}{1}.txt", AppDomain.CurrentDomain.BaseDirectory, DateTime.Now.ToString("MMddHHmmssfff")); } while (File.Exists(resultpath)); StreamWriter writer = new StreamWriter(resultpath); while (value1.HasValue && value2.HasValue) { if (value1 < value2) { writer.WriteLine(value1); value1 = GetValue(read1); } else { writer.WriteLine(value2); value2 = GetValue(read2); } } while (value1.HasValue) { writer.WriteLine(value1); value1 = GetValue(read1); } while (value2.HasValue) { writer.WriteLine(value2); value2 = GetValue(read2); } queue.Enqueue(resultpath); read1.Close(); read1.Dispose(); read2.Close(); read2.Dispose(); writer.Close(); writer.Dispose(); }
可以看出思路其实很简单。首先把大量数据细分为N个小块（相当于图书馆划分区域）。然后这N个小块各自进行排序（相当于划分完区域后开始点算书籍数量）。最后再把结果聚集起来。
下回将介绍使用压缩的方式在内存中对大量数据进行排序的思路。