Parallel comparison merging of many-ordered lists

AbstractWe consider the problem of merging m disjoint ordered lists, each of size n⧸/m. We determine up to a constant factor the worst case and average case deterministic and randomized parallel comparison complexity of the problem for all the range of n, m and p where p is the number of processors used. The worst case deterministic time complexity is Θlog mlog(1+p⧸n)+loglog nlog(2+p⧸n) That means Θn log mp+log log n for p⩽2n and Θlog mlog(p⧸n)+loglog nlog(p⧸n)for p⩾2n Clearly merging two equal lists and sorting are special cases of this problem for m = 2 and m = n respectively. We also prove that these bounds hold for randomized algorithms and even for the average case of deterministic or randomized ones. Therefore the average case of the best deterministic or randomized algorithm for this problem is not faster than the worst case of the best deterministic one by more than a constant factor