A Partitioning Approach to the Design of Selection Networks

The (m,n) selection problem is defined as the selection of the m smallest numbers in any order from a set of n numbers (m ≤n). In this paper, we have proposed a class of design procedures for selection networks based on partitioning. Conditions are defined so that the optimal design can be found in polynomial time. The resulting selection network has O([log2n] · [log2m]) time complexity and O(n · [log²/2m]) hardware complexity for all values of m. As a comparison, networks previously known can optimize either hardware or delay but not both simultaneously, and perform worse than pure sorting when m approaches n/2.