A Partitioning Selection Algorithm on Multiprocessors

The so-called(m,n)selection problem is the problem of selecting the m smallest(orlargest)elements from n 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 thesemachines.The parallel selection algorithm has been successful on networks,but seldom studiedon the multiprocessing systems.This paper,based on a partitioning approach,proposes apartitioning algorithm of selection on multiprocessors using Valiant’s merging and sortingschemes.By means of this algorithm,(m,n)selection problem can be completed in parallel n/2processors in time O(loguloglogm-log(n/m)loglog(n/m)).