July 31, 1998 Updated by Ms. Jade Y.S. Hsu
Vol.1 No.1, pp.59-71 (January 1985)

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.

JISE

  1. A Semantic-Syntactic Approach to Image Analysis
  2. Imprecise Database, Imprecise Queries and View Navigation
  3. A New Thinning Algorithm for Removing Noise-Spurs and Retaining End-points
  4. The Optimality of the Number of k-Sorters of a Parallel Merging Algorithm
  5. On Properties of Extended LL(k) Grammars
  6. Pattern Recognition by Dynamic Look-up-Table Programming -The Dynamic Pyramid Approach