ON COST-OPTIMAL MERGE OF TWO INTRANSITIVE SORTED SEQUENCES
Jie Wu, Stephen Olariu · International Journal of Foundations of Computer Science · 2003
The problem of merging two intransitive sorted sequences (that is, to generate a sorted total order without the transitive property) is considered. A cost-optimal parallel merging algorithm is proposed under the EREW PRAM model. This algorithm has a run time of O( log 2 n) using O(n/ log 2 n) processors. The cost-optimal merge in the strong sense is still an open problem.