PARALLEL COMPARISON MERGING OF MANY-ORDERED LISTS

作     者：AZAR, Y 

作者机构：Department of Computer Science Building 460 Stanford University Stanford CA 94305 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：1991年第83卷第2期

页      面：275-285页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Computer Systems Programming 

摘      要：We 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 [GRAPHICS] That means [GRAPHICS] and [GRAPHICS] 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.