A parallel implementation of merge sort on a CREW PRAM (concurrent-read exclusive-write parallel random access machine) is given that uses n processors and O(log n) time; the constant in the running time is small. Also given is a more complex version of the algorithm for the EREW (exclusive-read exclusive-write) PRAM; it also uses n processors and O(log n) time. The constant in the running time is still moderate, though not as small.
|Original language||English (US)|
|Title of host publication||Annual Symposium on Foundations of Computer Science (Proceedings)|
|Number of pages||6|
|State||Published - Dec 1 1986|
|Name||Annual Symposium on Foundations of Computer Science (Proceedings)|
ASJC Scopus subject areas
- Hardware and Architecture