摘要
Batcher排序网络在排序深度上不是最优的,但由于有较好的并行性和时间复杂度,因此许多并行排序算法都基于Batcher排序网络.通过观察Batcher奇偶排序网络,提出在SIMD SM模型上的一种奇偶排序算法.该算法占用n/2个处理器,在○(log22n)时间里排序n个关键字.
Batcher sorting network is not optimal in sorting depth.Many parallel sorting algorithms are based on the Batcher sorting network because of its inherent parallelism and fast time complexity.This paper presents a parallel oddeven sorting algorithm for SIMDSM by observing Batcher oddeven sorting network.The proposed algorithm has a capability of sorting n keys in ○(log22n)time with ○(n/2)processors.
出处
《西北师范大学学报（自然科学版）》
CAS
2003年第3期33-35,共3页
Journal of Northwest Normal University(Natural Science)
基金
甘肃省自然科学基金资助项目(ZS001 A22 017 G)
