Parallel sorting system to reduce the amount of communication between

Abstract

A parallel sorting system is disclosed, having N (=2.sup.n) processing devices, each of which comprises a sort element storing unit, an inner sorting unit, a transposing unit, and a comparing and substituting unit. In the sort element storing unit, sort elements/N are stored. Sorting process is performed for n stages. In each stage, the inner sorting unit sorts the sort elements, and the transposing unit exchanges sorted elements at a transposing position with another processing device through a network. Thereafter, the comparing and substituting unit compares the two sets of sorts elements. This process sequence is repeated for all stages. And, after the transposing process and the inner sorting process are performed, the sorting process are completed. In this system, the number of communication times is reduced to 2n.