本文转自https://www.cnblogs.com/huangxincheng/archive/2012/12/19/2824943.html  

说到排序，大家第一反应基本上是内排序，是的，算法嘛，玩的就是内存，然而内存是有限制的，总有装不下的那一天，此时就可以来玩玩

外排序，当然在我看来，外排序考验的是一个程序员的架构能力，而不仅仅局限于排序这个层次。

一：N路归并排序

1.概序

    我们知道算法中有一种叫做分治思想，一个大问题我们可以采取分而治之，各个突破，当子问题解决了，大问题也就KO了，还有一点我们知道

内排序的归并排序是采用二路归并的，因为分治后有LogN层，每层两路归并需要N的时候，最后复杂度为NlogN，那么外排序我们可以将这个“二”

扩大到M，也就是将一个大文件分成M个小文件，每个小文件是有序的，然后对应在内存中我们开M个优先队列，每个队列从对应编号的文件中读取

TopN条记录，然后我们从M路队列中各取一个数字进入中转站队列，并将该数字打上队列编号标记，当从中转站出来的最小数字就是我们最后要排

序的数字之一，因为该数字打上了队列编号，所以方便我们通知对应的编号队列继续出数字进入中转站队列，可以看出中转站一直保存了M个记录，

当中转站中的所有数字都出队完毕，则外排序结束。如果大家有点蒙的话，我再配合一张图，相信大家就会一目了然，这考验的是我们的架构能力。

图中这里有个Batch容器，这个容器我是基于性能考虑的，当batch=n时，我们定时刷新到文件中，保证内存有足够的空间。

扩展

leveldb应用

在 LevelDB 数据库中高层数据下沉到低层时需要经历一次 Major Compaction，将高层文件的有序键值对和低层文件的多个有序键值对进行归并排序。磁盘多路归并排序算法的输入是来自多个磁盘文件的有序键值对，在内存中将这些文件的键值对进行排序，然后输出到一到多个新的磁盘文件中。

多路归并排序在大数据领域也是常用的算法，常用于海量数据排序。当数据量特别大时，这些数据无法被单个机器内存容纳，它需要被切分位多个集合分别由不同的机器进行内存排序（map 过程），然后再进行多路归并算法将来自多个不同机器的数据进行排序（reduce 过程），这是流式多路归并排序，为什么说是流式排序呢，因为数据源来源于网络套接字。

多路归并排序的优势在于内存消耗极低，它的内存占用和输入文件的数量成正比，和数据总量无关，数据总量只会线性正比影响排序的时间。

下面我们来亲自实现一下磁盘多路归并算法，为什么是磁盘，因为它的输入来自磁盘文件。

算法思路

我们需要在内存里维护一个有序数组。每个输入文件当前最小的元素作为一个元素放在数组里。数组按照元素的大小保持排序状态。

接下来我们开始进入循环，循环的逻辑总是从最小的元素下手，在其所在的文件取出下一个元素，和当前数组中的元素进行比较。根据比较结果进行不同的处理，这里我们使用二分查找算法进行快速比较。注意每个输入文件里面的元素都是有序的。

1. 如果取出来的元素和当前数组中的最小元素相等，那么就可以直接将这个元素输出。再继续下一轮循环。不可能取出比当前数组最小元素还要小的元素，因为输入文件本身也是有序的。

2. 否则就需要将元素插入到当前的数组中的指定位置，继续保持数组有序。然后将数组中当前最小的元素输出并移除。再进行下一轮循环。

3. 如果遇到文件结尾，那就无法继续调用 next() 方法了，这时可以直接将数组中的最小元素输出并移除，数组也跟着变小了。再进行下一轮循环。当数组空了，说明所有的文件都处理完了，算法就可以结束了。

值得注意的是，数组中永远不会存在同一个文件的两个元素，如此才保证了数组的长度不会超过输入文件的数量，同时它也不会把没有结尾的文件挤出数组导致漏排序的问题。

思维导图：

外部归并排序的原理：

第一步：
第二步：

问题：内存缓存区大小固定，外存数据元素分块后仍然无法将俩块放入比较
答：因为归并段已经块内有序，所以只需要将归并段部分装入内存，比较每个归并段相同位置元素的先后次序写入结果集即可
例：有俩个归并段1358和2467，每个缓存区可以存放2个数据元素
1、先将俩个个归并段的前俩个数据元素写入内存
2、然后12比较输出1，缓存区1标记后移；23比较输出2，标记后移；
3、输出缓存区满，写入外存
4、然后34比较输出3，缓存区1比较完毕清空，将后俩个数据元素放入继续比较
5、重复上述的过程直到比较结束

外部归并排序的性能：

归并段个数 * 每个归并段内部排序时间 + 磁盘IO读写的次数 * 每个归并块读写的时间 + 归并趟数 * 比较次数

3：排序成归并块的读写、俩次归并排序的读写
(4+4) : 四次读 + 四次写

ps： IO读写的时间 >> 内部排序时间，所以优化外部归并排序，就要减少IO读写次数
问题： 如何减少IO读写次数？
答： 二路归并排序变四路归并排序

总时间主要是受 外存读写时间的控制，而外存读写时间受归并趟数的影响，所以，要想减少总时间，就要减少归并趟数（多路归并）

归并排序法的优化：

1、让K值增大

1、即增加归并路数(会增加关键字对比次数，即增加内部排序时间)
2、用败者树减少关键字对比次数

2、让r减小

1、增大每块缓冲区容量
2、用“置换-选择排序”减少初始归并段数量

目录

前言

外排序

背景

概念

归并外排序

测试

前言

本章主要讲解：

归并外排序的操作以及实现（C语言）

注：本章需要用到文件操作的知识，如果有问题，可以先浏览学习一下文件操作的知识：⭐️ C语言进阶 ⭐️ 文件操作超详解【 建议关注+收藏 】

外排序

背景

• 实现代码：

//归并外排序
void Mergefile(const char* fin1, const char* fin2, const char* fmerge)
{
	//以写入的方式创建合并后的新临时文件
	FILE* fout = fopen(fmerge, "w");
	if (fout == NULL)
	{
		perror("fopen fout fail\n");
		exit(-1);
	}
	//以读取的方式打开合并子文件
	FILE* file1 = fopen(fin1, "r");
	if (file1 == NULL)
	{
		perror("fopen file1 fail\n");
		exit(-1);
	}
	FILE* file2 = fopen(fin2, "r");
	if (file2 == NULL)
	{
		perror("fopen file2 fail\n");
		exit(-1);
	}
	//归并排序文件数据
	int num1, num2;
	int ret1 = fscanf(file1, "%d\n", &num1);//文件成功读取，读取指针则自动往后走
	int ret2 = fscanf(file2, "%d\n", &num2);//所以保存返回结果，比较数据写入后再读取文件
	while (ret1 != EOF && ret2 != EOF)
	{
		if (num1 < num2)
		{
			//写入数据并读取下一个数据
			fprintf(fout, "%d\n", num1);
			ret1 = fscanf(file1, "%d\n", &num1);
		}
		else
		{
			fprintf(fout, "%d\n", num2);
			ret2 = fscanf(file2, "%d\n", &num2);
		}
	}
	while (ret1 != EOF)
	{
		fprintf(fout, "%d\n", num1);
		ret1 = fscanf(file1, "%d\n", &num1);
	}
	while (ret2 != EOF)
	{
		fprintf(fout, "%d\n", num2);
		ret2 = fscanf(file2, "%d\n", &num2);
	}
	fclose(file1);
	fclose(file2);
	fclose(fout);
}

void MergeSortFile(const char* file, int N, int Num)
{
	//以读取的方式打开数据文件
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail\n");
		exit(-1);
	}
	//开辟额外空间来接收数据
	int* arr = malloc(sizeof(int) * Num);
	if (arr == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	//把大文件划分成小文件，并排序
	char subfile[100];//小文件名
	int filei = 1, i=0, num;
	while(fscanf(fout, "%d\n", &num) != EOF)
	{
		if (i < Num - 1)
		{
			arr[i++] = num;//载入内存
		}
		else//再入够数据进行排序，对排序好的数据输出到临时文件中
		{
			arr[i] = num;
			QuickSort(arr, 0, Num-1);//排序
			//排好后写入文件
			sprintf(subfile, "Sortedfile%d", filei++);//创建修改小文件名
			FILE* fin = fopen(subfile, "w");//以写入的方式创建小文件
			if (fin == NULL)//文件开辟失败
			{
				perror("fopen subfile fail\n");
				exit(-1);
			}
            //输出到文件中
			for (int j = 0; j < Num; j++)
			{
				fprintf(fin, "%d\n", arr[j]);//写入排好的数据
			}
			fclose(fin);
			i = 0;//更新记录读取数据的个数变量
		}
	}
	//开始进行合并数据文件
	char fin1[100] = "Sortedfile1";
	char fin2[100] = "Sortedfile2";
	char fmerge[100] = "Sortedfile12";
	for (i = 1; i < N; i++)
	{
		//归并文件
		Mergefile(fin1, fin2, fmerge);
		//更替文件名
		strcpy(fin1, fmerge);
		sprintf(fin2, "Sortedfile%d", i + 2);
		sprintf(fmerge, "%s%d", fmerge, i + 2);
	}
	fclose(fout);
	free(arr);
}

测试

• 测试代码：

int main()
{
	//获取随机种子
	srand(time(0));
	//创建待排序数据文件
	char file[100] = "datafile.txt";
	FILE* data = fopen(file, "w");
	if (data == NULL)
	{
		perror("fopen fail\n");
		exit(-1);
	}
	//将随机数写进写入文件
	const n = 10, num = 5000;
	for (int i = 0; i < n * num; i++)
	{
		fprintf(data, "%d\n", rand());
	}
	fclose(data);
	//排序
	MergeSortFile(file, n, num);

	return 0;
}

• 测试结果：

 看来归并外排序实现的还是非常成功的！！