并行归并排序算法

A PARALLEL MERGING/SORTING ALGORITHM

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

Abstract: It is noticeable to make up a parallel algorithm whose efficiency is O（1）. 1 and 2show 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.