摘要
构造效率为O(1)的并行算法是一个引人注目的问题。[1]和[2]分别提出了并行度为O(logn)和O(n1/2)的、效率为O(1)的并行排序算法。本文提出一种新的并行排序算法,其效率为O(1),而并行步数少于[1]和[2]的算法的并行步数。经过改进后,在保持效率为O(1)的情况下,可进一步将并行度扩大到O(n1/2logn)。
It is noticeable to make up a parallel algorithm whose efficiency is O(1). [1] and [2]show two such parallel algorithms using O(log n) and O(n1/2) processors respectively. In this paper, a new parallel sorting algorithm is proposed. Its efficiency is O(1), and it works in much fewer steps. It can work in O(n 1/2) steps using O(n1/2 log n) processors after modification.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1995年第6期46-49,54,共5页
Journal of Computer Research and Development
关键词
并行度
并行排序算法
并行算法
Parallelism, determination of merging segments, determination of beginning elements, merging, joining.