什么是多相归并排序

多相归并排序是一种外部排序算法。给定 N 个磁带，只需要 1 个磁带作为输出设备。而且读写都是顺序的，对磁盘/磁带等外部存储设备更加友好。

归并排序
归并排序，其算法思想最终的结果是通过合并两个run（排序数据的缩写）得到的。
初始状态下，一个待排序的元素可以看成一个run，然后按照n次方逐渐合并2为基础。是最终的结果。显然，算法复杂度（时间）为O(nlogn)。

Tape1: 2 3 5 6 9 11Tape2: 4 7 8 10Output: 2 3 4 5 6 7 8 9 10 11 

Tape1: 2 3 5 6 30 | 1 11 200 磁带2：4 7 8 10 | 15 20 35 201Tape3 : EmptyTape4 : 空

通过1

Tape1 : EmptyTape2 : EmptyTape3 : 2 3 4 5 6 7 8 10 30 Tape4 : 1 11 15 20 35 200 201

通过 2

磁带 1 : 1 2 3 4 5 6 7 8 10 11 15 20 30 35 200 201 磁带 2 : 空磁带 3 : 空磁带 4 :空

之所以称为平衡，是因为输入和输出“设备”的数量相同。 N-way是指可以同时（并行）处理N个设备。
从空间利用率上来说，该算法需要N个空闲设备。

多相归并排序
多相归并排序与N路类似，但只需要1个空闲设备，大大节省了空间。
注意：如下wing 是一个实现示例，其中由字符“|”分隔的部分调用run

初始状态
Tape1: 2 3 5 6 30 | 1 11 200 | 25 40 56 70
磁带2：4 7 8 10 | 15 20 35 201 | 27 33 46 78 | 27 33 46 78 13 17 27 87 90
磁带3：空

Pass1
磁带1：空
磁带2：13 17 27 87 90
磁带3 : 2 3 4 5 6 7 8 10 30 | 1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78

通过 2
磁带 1：2 3 4 5 6 7 8 10 13 17 27 30 87 90
磁带 2：空
磁带3：1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78

通过3
磁带1：空
磁带2：1 2 3 4 5 6 7 8 10 11 13 15 17 20 27 30 35 87 90 200 201
磁带3：25 27 33 40 46 56 70 78

通过4
磁带1：1 2 3 4 5 6 7 8 10 11 13 15 17 20 25 27 30 33 35 40 46 56 70 78 87 90 200 201
磁带2：空
磁带3：空

此时，相信大家对《什么是多相归并排序》有了更深入的了解，不妨实践一下！这是网站。更多相关内容，您可以进入相关渠道进行查询。关注我们并继续学习！