A partitioning selection algorithm on multiprocessors
A Partitioning Selection Algorithm on Multiprocessors

The so-called (m, n) selection, problem is the problem of selecting them smallest (or largest) elements fromn given numbers (n>m). With the development of parallel computers, much attention has been paid to the design of efficient algorithms of (m, n) problem for these machines. The parallel selection algorithm has been successful on networks, but seldom studied on the multiprocessing systems. This paper, based on a partitioning approach, proposes a partitioning algorithm of selection on multiprocessors using Valiant’s merging and sorting schemes. By means of this algorithm, (m, n) selection problem can be completed in paralleln/2 processors in timeO (lognloglogm-log(n/m)loglog(n/m))1). This project is supported by National Natural Science Fundation of China.