We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(log n) time; the constant in the running time is small. We also give a more complex version of the algorithm for the EREW 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)|
|Number of pages||16|
|Journal||SIAM Journal on Computing|
|State||Published - 1988|
ASJC Scopus subject areas
- Computer Science(all)