Title :
Parallel merge sort
Abstract :
We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(logn) 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(logn) time. The constant in the running time is still moderate, though not as small.
Keywords :
Algorithm design and analysis; Circuits; Computational modeling; Graph theory; Merging; Parallel algorithms; Phase change random access memory; Radio access networks; Read-write memory; Sorting;
Conference_Titel :
Foundations of Computer Science, 1986., 27th Annual Symposium on
Conference_Location :
Toronto, ON, Canada
Print_ISBN :
0-8186-0740-8
DOI :
10.1109/SFCS.1986.41