| Constants in parallel sorting | |
| Author: | Jyrki Katajainen |
| Published in: | Proceedings of the 19th Australasian Computer Science Conference, Australian Computer Science Communications 18,1, Computer Science Association (Australia) (1996), 357-366 |
| Full text: |  PS (258 kB) |
| 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. |
| Related: |  HTML (Technical report) |
| BibLATEX: | @inproceedings{Kat1996aC,
author = {Jyrki Katajainen},
title = {Constants in parallel sorting},
booktitle = {Proceedings of the 19th Australasian Computer Science
Conference},
series = {Australian Computer Science Communications},
volume = {18},
number = {1},
publisher = {Computer Science Association (Australia)},
year = {1996},
pages = {357--366},
}
|