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¡EN k-sorter k-way merging algorithm proposed by Tseng and Lee is optimal up to a factor of k +£`.
This research work was partially supported by the National Science Council of the Republic of China under the contract NSC 74-0408-E007-01.