A Partitioning Selection Algorithm on Multiprocessors

The so-celled(m,n)-selection problem is the problem of selecting the m smallest(or largest) elements from n given numbers(n>m). With the development of parallel computers, much attention has been paid to the design of efficient algorithm of(m, n) problem for these machines. The parallel selection algorithm has been succesful on networks, but is seldom studied on multiprocessing systems. This paper, based on partitioning approach, proposes a partitioning selection algorithm on multiprocessors using Valiant's merging and sorting schemes. By means of this algorithm,(m, n)-selection problem can be completed in parallel n/2 processors in time O(lognloglogm).