并行归并排序算法  

A PARALLEL MERGING/SORTING ALGORITHM

作　　者：来智勇[1] 

机构地区：[1]西安交通大学管理学院会计系

出　　处：《计算机研究与发展》1995年第6期46-49,54,共5页Journal of Computer Research and Development

摘　　要：构造效率为Ｏ（１）的并行算法是一个引人注目的问题。［１］和［２］分别提出了并行度为Ｏ（ｌｏｇｎ）和Ｏ（ｎ１／２）的、效率为Ｏ（１）的并行排序算法。本文提出一种新的并行排序算法，其效率为Ｏ（１），而并行步数少于［１］和［２］的算法的并行步数。经过改进后，在保持效率为Ｏ（１）的情况下，可进一步将并行度扩大到Ｏ（ｎ１／２ｌｏｇｎ）。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.

关 键 词：并行度 并行排序算法 并行算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]