Polyphase Merge Sort是一种External Sort算法,给定N个Tapes,只需要1个Tapes作为Output设备,而且读写均为顺序读写,对于Disk/Tapes等外存设备比较友好. 在介绍Polyphase Merge Sort之前,有必要先行简要介绍Merge Sort/Balanced N-way Merge Sort. **Merge Sort** 归并排序,其算法思想是对于2个run(已排序的数据简称)进行归并得到最终结果. 在初始状态下,可以把一个待排序的元素视为一个run,然后以2的n次方为基数逐步归并为最终结果,显然,其算法复杂度(时间)是O(nlogn). ``` Tape1 : 2 3 5 6 9 11 Tape2 : 4 7 8 10 Output : 2 3 4 5 6 7 8 9 10 11 ``` **Balanced N-way Merge Sort** 平衡多路归并排序,其算法思想是使用N个输入和输出设备,读取N个输入归并产生N个输出. 注:下面是一个实现样例,其中以字符"|"分隔的部分称为run ``` Tape1 : 2 3 5 6 30 | 1 11 200 Tape2 : 4 7 8 10 | 15 20 35 201 Tape3 : Empty Tape4 : Empty ``` *Pass1* ``` Tape1 : Empty Tape2 : Empty Tape3 : 2 3 4 5 6 7 8 10 30 Tape4 : 1 11 15 20 35 200 201 ``` *Pass2* ``` Tape1 : 1 2 3 4 5 6 7 8 10 11 15 20 30 35 200 201 Tape2 : Empty Tape3 : Empty Tape4 : Empty ``` 之所以称为平衡,是因为输入和输出的"设备"是一样多的.N-way指的是可以同时对N个设备进行处理(并行). 在空间利用上,这种算法需要N个空闲设备. **Polyphase Merge Sort** Polyphase Merge Sort与N-way类似,但只需要1个空闲设备,大大节省了空间. 注:下面是一个实现样例,其中以字符"|"分隔的部分称为run *初始状态* Tape1 : 2 3 5 6 30 | 1 11 200 | 25 40 56 70 Tape2 : 4 7 8 10 | 15 20 35 201 | 27 33 46 78 | 13 17 27 87 90 Tape3 : Empty *Pass1* Tape1 : Empty Tape2 : 13 17 27 87 90 Tape3 : 2 3 4 5 6 7 8 10 30 | 1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78 *Pass 2* Tape1 : 2 3 4 5 6 7 8 10 13 17 27 30 87 90 Tape2 : Empty Tape3 :1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78 *Pass3* Tape1 : Empty Tape2 : 1 2 3 4 5 6 7 8 10 11 13 15 17 20 27 30 35 87 90 200 201 Tape3 :25 27 33 40 46 56 70 78 *Pass4* Tape1 : 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 Tape2 : Empty Tape3 : Empty