NobleBlocks

Research indexJournal article

Space-efficient parallel merging

Katajainen, Levcopoulos, Petersson

RAIRO - Theoretical Informatics and Applications1 Jan 1993Open access

NobleIDark:/48914/w1/20260525/5803A047DOI10.1051/ita/1993270402951

Abstract

The problem of designing space-efficient parallel mer ging algorithms is examined. It is shown that two sorted squences 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 + log log 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.

Discussion

Citations

Topics

More

Suggest a correction or report