各类排序方法在时间、空间复杂度及稳定性（通俗地讲，就是两个相等的数不会交换位置）方面各有优势：

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

K-路合并问题包括合并K排序数组以产生具有相同元素的单个排序数组。

该问题可以通过使用2路合并迭代合并两个K数组直到只剩下一个数组来合并。

1 算法流程

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

1.2 首先读取每个流的第一个数，如果已经EOF，pass；

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

1.4 直到所有K路都EOF。

2 多路归并

2.1 循环遍历

首先，我们比较所有k个数组的头一个元素，找到最小的那一个，然后取出来。我们在该最小元素所在的数组取下一个元素，然后重复前面的过程去找最小的那个。这样依次循环直到找到所有的元素。

用一个notEmpty来标志所有序列是否已经遍历完了。每次遍历所有序列的当前元素，找到最小的。这样每次找一个元素都要比较k次，假设所有n个元素，其总体时间复杂度就达到了O(nk)。

2.2 最小堆K路归并排序

首先从k路序列中都取一个元素出来。因为所有的都是已经按照从小到大排序的，不需要考虑其他的。每个序列里取出来的肯定是这个序列里最小的，在这些最小元素里找到全局最小的那个。针对这个序列后面是否还有元素的问题，可以通过以下两种方法处理：

I 假定在处理元素的过程中，某个序列的元素取光了。我们可以在开始的时候针对所有序列的最后都加一个表示无穷大的数值。这样如果取完这个序列之后可以保证它后续肯定不会被选择到。

II 我们将该元素用堆最后的元素替换，然后调整堆的属性并将堆的大小减1。这样我们这个大小为k的堆慢慢会变成k-1, k-2 …… ,1这些个长度的堆。一直到我们把这些堆里序列的元素处理完 。

2.3 胜者树K路并归排序

首先，胜者树的形式如图：

几乎堆的每个叶节点对应一个输入序列，将其构成一个完全二叉树，进行一轮胜者的选择之后，对结构如下：

可以看出最终在堆顶的那个元素是最小的，而且有一条路径从叶节点到堆的根。

通过在原来序列里取后续的元素，然后像胜者树调整一样向上，符合条件的元素放上面，然后一直比较到根。这样就找到了下一个最小的元素。这样一直循环下去。如果一个序列处理完了我们可以采用在末尾增加一个无穷大的值。

总的来说，这个方法和普通的最小堆调整差不多，就是调整的方式不一样而已 。

2.4 败者树K路并归排序

叶子节点记录k个段中的最小数据，然后两两进行比赛。败者树是在双亲节点中记录下刚刚进行完的这场比赛的败者，让胜者去参加更高一层的比赛。决赛，根节点记录输者，所以需要重建一个新的根节点，记录胜者。

I 创建败者树

叶子节点记录k个段中的最小数据，然后两两进行比赛。败者树是在双亲节点中记录下刚刚进行完的这场比赛的败者，让胜者去参加更高一层的比赛。决赛，根节点记录输者，所以需要重建一个新的根节点，记录胜者(如下图节点0）。

示例：我们这里以四路归并为例，假设每个归并段已经在输入缓冲区如下图。

II 调整败者树

每路的第一个元素为胜利树的叶子节点，（5,7）比较出5胜出7失败成为其根节点，（29,9）比较9胜出29失败成为其根节点，胜者（5,9）进行下次的比赛9失败成为其根节点5胜出输出到输出缓冲区。由第一路归并段输出，所有将第一路归并段的第二个元素加到叶子节点如下图：

加入叶子节点16进行第二次的比较，跟胜利树一样，由于右子树叶子节点没有发生变化其右子树不用再继续比较。

3 C++代码

输出：

5 5 5 5 4

5 5 3 5 4

5 5 3 2 4

5 1 3 2 4

3 1 0 2 4

6 9 10 10 11 12 15 15 16 18 20 25 37

4 代码分析

4.1 创建败者树

把败者树分为两部分：

第一部分是b[]，用来保存K路数组的首元素，叶节点存放在此处；

第二部分式ls[],用来保存败者数组的下标，b[0]是最终的胜者(即所求的数)，败者节点存放在此处；

4.2 调整败者树

将新补充的节点与其父节点进行比较，败者留在该父节点上，胜者继续向上直至根节点

附代码：

#include <iostream>using namespace std;const int MINKEY = 0;//假设给定数组中所有数都大于0const int MAXKEY = 200;//假设给定数组中所有数都小于200//完全二叉树的叶子节点个数比度为2的节点个数多1void Adjust(int &k, int* &ls, int* &b, int i){ //控制非叶子结点ls[]的下标 int t = (i + k) / 2;//第一个非叶子结点的下标、第二个…… //控制叶子结点b[]的下标 int s = i; for (; t > 0; t /= 2){ if (b[ls[t]]<b[s]){ swap(s, ls[t]); } else{ s = s; } } ls[0] = s;}void createLoserTree(int* arr[],int &k, int* &ls, int* &b){ for (int i = 0; i < k; ++i) b[i] = arr[i][0]; b[k] = MINKEY; for (i = 0; i < k; ++i) ls[i] = k;	//最小值（绝对的胜者）的序号 //有k个叶子节点 //从最后一个叶子节点开始，沿着从叶子节点到根节点的路径调整 for (i = k - 1; i >= 0; --i){ Adjust(k, ls, b, i); for (int i = 0; i < k; ++i) cout << ls[i] << " "; cout << endl; }}void kMerge(int* arr[], int* arrayElementsCount, int& k, \			int* &ls, int* &b, int& mostMinCount){ int* index = new int[k]; for (int i = 0; i < k; ++i) index[i] = 0; for (i = 0; i < mostMinCount; ++i){ int s = ls[0]; cout << b[s] << " "; ++index[s]; if (index[s] < arrayElementsCount[s]) arr[s][0] = arr[s][index[s]]; else arr[s][0] = MAXKEY; b[s] = arr[s][0]; Adjust(k, ls, b, s); } delete[] index;}int main(){ int arr0[] = { 6, 15, 25 }; int arr1[] = { 12, 37, 48, 50 }; int arr2[] = { 10, 15, 16 }; int arr3[] = { 9, 18, 20 }; int arr4[] = { 10, 11, 40 }; int* arr[] = { arr2, arr3, arr4, arr0, arr1 }; int* arrayElementsCount = new int[5]; arrayElementsCount[0] = sizeof(arr2) / sizeof(arr2[0]); arrayElementsCount[1] = sizeof(arr3) / sizeof(arr3[0]); arrayElementsCount[2] = sizeof(arr4) / sizeof(arr4[0]); arrayElementsCount[3] = sizeof(arr0) / sizeof(arr0[0]); arrayElementsCount[4] = sizeof(arr1) / sizeof(arr1[0]); int k = sizeof(arr) / sizeof(arr[0]); //记录每个数组的首元素 int* b = new int[k + 1]; //记录败者的下标 int* ls = new int[k]; createLoserTree(arr, k,ls,b); int mostMinCount = 13; kMerge(arr, arrayElementsCount, k, ls, b, mostMinCount); delete[] b; delete[] ls; delete[] arrayElementsCount; system("pause");}

－End－