Constants in parallel sorting
Jyrki Katajainen
Department of Computer Science,
University of Copenhagen,
Universitetsparken 1,
DK-2100 Copenhagen East, Denmark
jyrki@diku.dk
Abstract
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