Constants in parallel sorting

Jyrki Katajainen
Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen East, Denmark


The constant factors in the time complexity of three parallel mergesort variants, running on an EREW PRAM, are analysed under a simple cost model. The algorithms studied are linear-time mergesort, odd-even mergesort and polylogarithmic mergesort. The processors of a PRAM are assumed to be word-addressable machines that can execute three-address instructions of our hypothetical assembly language in unit time. For the sake of comparison, sequential quicksort, heapsort and mergesort are examined within the same framework. The number of operations performed by linear-time mergesort, i.e. its work, is at most four times the time required by sequential mergesort. The work of polylogarithmic mergesort is about twenty times that of sequential mergesort. Moreover, polylogarithmic mergesort seems to perform relatively well compared to odd-even mergesort, but there are still place for improvements.
Conference Home Page