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

• 作者: 刘志勇 赵立军
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 归并 排序 多路归并 排序网络
• 年，卷（期）: 1999,（4）
• 所属期刊栏目: 软件技术
• 页码范围: 417-422
• 页数: 6页
• 分类号: TP301
• 字数: 3639字
• 语种: 中文

摘要

文中提出了一种新的多路归并排序网络,该网络基于倾斜与振荡多路归并排序算法.该网络有两个主要特点.一是其基本构件为k-sorters,即k个数的排序器,k为任意素数,而传统的排序网络的基本构件为两个数的排序,即2-sorters.二是该网络的延迟可以小于传统的基于2-sorters的Batcher排序网络.文中给出了该排序网络的具体实现;作为实例给出了N=27,k=3时的排序网络;分析了该网络的时间延迟;通过具体设计排序网络的基本构件2-sorters和3-sorters,表明这种新的多路归并排序网络和Batcher排序网络相比是一种高速的排序网络.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘志勇	中国科学院计算技术研究所	48	393	11.0	18.0
2	赵立军	中国科学院计算技术研究所	3	87	2.0	3.0