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.gif>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, mn, 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.gif>HTML (Technical report)  <html.gif>HTML (Conference paper)  
  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},
This page was generated by Jyrki Katajainen <> on 2018-11-09.