The Optimality of the Number of K-Sorters of a Parallel Merging Algorithm
S. S. Tseng and R. C. T. Lee* Institute of Computer Engineering, National Chiao Tung University, Hsinchu, Taiwan 300, Republic of China, * Department of Electrical Engineering, National Tsing Hua University, Hsinchu, Taiwan 300, Republic of China
In this paper, we shall show the lower bound of the number of k-sorters needed for a non-adaptive parallel merging algorithm. We then show that the number of k-sorters used in the k‧N k-sorter k-way merging algorithm proposed by Tseng and Lee is optimal up to a factor of k +ε.