In this paper we propose a new parallel sorting algorithm which is based upon an operation which sorts three elements. This algorithm is similar to the parallel odd-even merge sorting algorithm proposed by Batcher, except in the latter, the basic operation sorts only two elements. The correctness of our algorithm is also proved.
This research work was partially supported by a grant from the National Science Council, Republic of China under the contract NSC73-0201-E007-01.
