A Bitonic Selection Algorithm on Multiprocessor System

The so-called (m, n) selection problem is defined as the selection of the m smallest (or largest) numbers from n given numbers (n>m). Solving this problem in parallel mode has been successful on the networks, but it is seldom studied on the multiprocessor systems. This paper first, based on Batcher's principle of bitonic merging, proposes the bitonic selection network. Then it repeals the varying rule of the pivots in all successive ranks of the network through our observation to the data transfer property in the network. Finally, according to this rule, the parallel selection algorithm with running time O (lognlogm)¹⁾ on n processors is presented.