Some Sorting Algorithms for Parallel Machines

Two algorithms to perform sorting on parallel machines are presented. The first is a modified version of Batcher’s merge-exchange sort, but with an explicitly recursive structure involving fewer data passing operations between distant processors. The other is a version of the radix sort, which does not require the array elements to be moved between processors, but gradually computes the sequence number of each element using bit-serial counting.