多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。

(1)假设有K路数据流，流内部是有序的，且流间同为升序或降序

(2)首先读取每个流的第一个数，如果已经EOF，pass

(3)将有效的k(k可能小于K)个数比较，选出最小的那路mink，输出，读取mink的下一个

(4)直到所有K路都EOF

代码如下：

/*
 * main.c
 *
 *  Created on: 2011-11-11
 *      Author: liheyuan
 */

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef int TYPE;

#define MIN_MAX 8888

void k_merge(TYPE** arrs, int* lens, int k)
{
	int* cnts = (int*) malloc(sizeof(int) * k);
	int* has_next = (int*) malloc(sizeof(int) * k);
	TYPE* datas = (int*) malloc(sizeof(int) * k);
	int i;
	int min_index = 0;
	TYPE min;

	//Read each k-way first into data
	for (i = 0; i < k; i++)
	{
		if (lens[i] >= 1)
		{
			datas[i] = arrs[i][0];
			cnts[i] = 1;
			has_next[i] = 1;
		}
		else
		{
			has_next[i] = 0;
		}
	}

	while (1)
	{

		//Select min in k
		min = MIN_MAX;
		min_index = 0;
		for (i = 0; i < k; i++)
		{
			if (has_next[i])
			{
				if (datas[i] < min)
				{
					min = datas[i];
					min_index = i;
				}
			}
		}

		if (min == MIN_MAX)
		{
			//No way has data
			break;
		}
		else
		{
			//print
			printf("%d\n", datas[min_index]);

			//Succ get one min
			if (cnts[min_index] < lens[min_index])
			{
				datas[min_index] = arrs[min_index][cnts[min_index]];
				cnts[min_index]++;
			}
			else
			{
				has_next[min_index] = 0;
			}
		}
	}

	free(cnts);
}

//void k_merge(TYPE** arrs, int* lens, int k)

int main()
{
	TYPE a[5] =
	{ 1, 3, 5, 7, 17 };
	TYPE b[3] =
	{ -1, 10, 20 };
	TYPE c[4] =
	{ -20, 30, 88, 111 };
	TYPE* arrs[3] =
	{ a, b, c };
	int lens[3] =
	{ 5, 3, 4 };

	k_merge(arrs, lens, 3);

	return 0;
}

输出：

-20
-1
1
3
5
7
10
17
20
30
88
111