一种新的多路归并排序网络

AN EFFICIENT MULTIWAY MERGING SORTING NETWORK

摘要: 文中提出了一种新的多路归并排序网络，该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ，即ｋ个数的排序器，ｋ为任意素数，而传统的排序网络的基本构件为两个数的排序，即２－ｓｏｒｔｅｒｓ．二是该网络的延迟可以小于传统的基于２－ｓｏｒｔｅｒｓ的Ｂａｔｃｈｅｒ排序网络．文中给出了该排序网络的具体实现；作为实例给出了Ｎ＝２７，ｋ＝３时的排序网络；分析了该网络的时间延迟；通过具体设计排序网络的基本构件２－ｓｏｒｔｅｒｓ和３－ｓｏｒｔｅｒｓ，表明这种新的多路归并排序网络和Ｂａｔｃｈｅｒ排序网络相比是一种高速的排序网络．

Abstract: A new efficient multiway merging sorting network is proposed,which is based on sloping and shaking multiway merging sorting algorithm.Its basic component is k sorters,i.e.,the k elements sorter.The concrete implementation of the multiway merging sorting network is discussed,and its delay time is analyzed.It is shown that compared with the Batcher sorting network,it is an efficient multiway merging sorting network.It has less delay time than the Batcher sorting network if specific design of k sorters is adopted.