Optimal parallel merging algorithms on BSR
Limin Xiang, K. Ushijima · 2002
Merging is one of the most fundamental problems in computer science. It is well known that Ω(N/p+loglogN) time is required to merge two sorted sequences each of length N on CRCW PRAM with p processors, where pαN for any constant α. We describe two optimal O(1) time solutions to the problem for p = N on BSR (Broadcasting with Selective Reduction). They are the first constant time solutions to the problem on any model of computation. We also give an optimal solution to the problem for p < N on BSR with O(N/p) time, which is the first improvement with non-constant time but still better than the lower bound for PRAM.