| Space-efficient parallel merging | |
| Authors: | J. Katajainen, C. Levcopoulos, and O. Petersson |
| Published in: | RAIRO—Theoretical Informatics and Applications 27,4 (1993), 295–310 |
| Full text: |  HTML |
| Copyright: | © AFCET-Gauthier-Villars |
| Abstract: | The problem of designing space-efficient parallel merging algorithms is examined. It is shown that two sorted sequences of lengths m and n, m ≤ n, can be merged in O(n / p + log n) time on an EREW PRAM with p processors, using only a constant amount of extra storage per processor. After a slight modification, the algorithm runs on a DCM (Direct Connection Machine) within the same resource requirements. Moreover, using similar techniques, it is shown that merging can be accomplished in O(n / p + loglog m) time on a CREW PRAM with p processors, and 0(1) extra space per processor. Our algorithms use a sequential algorithm for in place merging as a subroutine; if this is stable, the parallel algorithms are stable as well. |
| Related: | HTML (Technical report) HTML (Conference paper) |
| BibLATEX: | @article{KLP1993J,
author = {Katajainen, J. and Levcopoulos, C. and Petersson, O.},
title = {Space-efficient parallel merging},
journaltitle = {RAIRO---Theoretical Informatics and Applications},
volume = {27},
number = {4},
year = {1993},
pages = {295--310},
}
|