A PARALLEL MERGING/SORTING ALGORITHM

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.