Startseite > Publikationen > Publikationen


Meyer auf der Heide, Friedhelm;Wigderson, Avi:

The Complexity of Parallel Sorting.

FOCS 1985 : S. 532-540, Jul. 1985


We consider PRAM's 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 require Ω(√(log n)) steps in this strong model.
We also show that computing any symmetric polynominal (e.g. the sum or product) of n integers requires exactly log_2(n) steps, for any finite number of processors.


author = {Meyer auf der Heide, Friedhelm and Wigderson, Avi},
title = {The Complexity of Parallel Sorting},
journal = {FOCS 1985},
pages = {532-540},
month = jul,
year = {1985},

BibTeX in die Zwischenablage kopieren