Parallel comparison merging of many-ordered lists (Q807015)

The paper deals with the analysis of the parallel algorithms for merging m disjoint ordered lists, each of size n/m. The problem is studied for the parallel comparison model with p parallel processors performing p comparisons in each time unit. Two theorems are proved. The first establishes the worst case time complexity for the given problem: \(\theta\) ((log m)/log(1\(+p/n)+\log ((\log n)/\log (2+p/n))\). This embodies the apriori known results for merging two equal lists \((m=2)\) and for sorting \((m=n)\). The second result shows that the average case complexity for the best randomized or deterministic parallel algorithm is the same, up to a constant factor, as the worst case complexity of the best deterministic one. This result is a generalization of a similar one given for sorting by the same author in a previous paper.