COMPLEXITY OF PARALLEL SORTING.

The authors consider PRAMs with arbitrary computational power for individual processors, infinitely large shared memory and priority write-conflict resolution. The main result is that sorting n integers with n processors requires OMEGA ( ROOT log n) steps in this strong model. It is also shown that computing any symmetric polynomial (e. g. , the sum or product) of n integers requires exactly log//2n steps, for any finite number of processors.