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,
*

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.

- A Semantic-Syntactic Approach to Image Analysis

- Imprecise Database, Imprecise Queries and View Navigation

- A New Thinning Algorithm for Removing Noise-Spurs and Retaining End-points

- The Optimality of the Number of
*k*-Sorters of a Parallel Merging Algorithm

- On Properties of Extended
*LL(k)*Grammars

- Pattern Recognition by Dynamic Look-up-Table Programming -The Dynamic Pyramid Approach