Sorting-based selection algorithms for hypercubic networks

This paper presents several deterministic algorithms for selecting the kth largest record from a set of n records on any n-node hypercubic network. Al l of the algorithms are based on the selection algorithm of Cole and Yap, a s well as on various sorting algorithms for hypercubic networks. Our fastes t algorithm runs in O(lg n lg* n) time, very nearly matching the trivial n( lg n) lower bound. Previously, the best upper bound known for selection was O(lgn lg lg n). A key subroutine in our O(lgn lg* n) time selection algori thm is a sparse version of the Sharesort algorithm that sorts n records usi ng p processors, p greater than or equal to n, in O(lg n(lg lg p lg lg(p/n) )(2)) time.