An Optimal Parallel Sorting Algorithm

The problem of sorting a sequence of n elements on a parallel computer with p processors is considered. 2 shows an algorithm of speed-up ratio of p for p≤log n. The algorithms we present can all be run on a single-instruction stream multiple-data stream computer For p≤n^1/2, each achieves a speed-up ratio of p which is optimal in the number of processors used.