Time-space optimal parallel merging and sorting
X. Guan, Michael Allen Langston · IEEE Transactions on Computers · 1991
The authors present a parallel merging algorithm that, on an exclusive-read exclusive-write (EREW) parallel random-access machine (PRAM) with k processors merges two sorted lists of total length n in O(n/k+log n) time and constant extra space per processor, and hence is time-space optimal for any value of k>