摘要
文中提出了一种新的多路归并排序网络，该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ，即ｋ个数的排序器，ｋ为任意素数，而传统的排序网络的基本构件为两个数的排序，即２－ｓｏｒｔｅｒｓ．二是该网络的延迟可以小于传统的基于２－ｓｏｒｔｅｒｓ的Ｂａｔｃｈｅｒ排序网络．文中给出了该排序网络的具体实现；作为实例给出了Ｎ＝２７，ｋ＝３时的排序网络；分析了该网络的时间延迟；通过具体设计排序网络的基本构件２－ｓｏｒｔｅｒｓ和３－ｓｏｒｔｅｒｓ，表明这种新的多路归并排序网络和Ｂａｔｃｈｅｒ排序网络相比是一种高速的排序网络．
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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1999年第4期417-422,共6页
Journal of Computer Research and Development
关键词
多路归并
排序网络
算法
计算机
merging, sorting, multiway merging, sorting network
