Parallel merge sort. (English) Zbl 0651.68077

Cole, Richard

SIAM J. Comput. 17, No. 4, 770-785 (1988).

Summary: 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.

MSC:

68P10	Searching and sorting
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q25	Analysis of algorithms and problem complexity

Keywords:

parallel algorithm; merge sort; CREW PRAM; EREW PRAM