Sorting and selection on interconnection networks
Sanguthevar Rajasekaran · DIMACS series in discrete mathematics and theoretical computer science · 1995
. In this paper we identify techniques that have been employed in the design of sorting and selection algorithms for various interconnection networks. We consider both randomized and deterministic techniques. Interconnection Networks of interest include the mesh, the mesh with fixed and reconfigurable buses, the hypercube family, and the star graph. For the sake of comparisons, we also list PRAM algorithms. 1 Introduction The problem of sorting a given sequence of n keys is to rearrange this sequence in nondecreasing order. Given a sequence X of n keys, and an integer i (1 i n), the problem of selection is to find the ith smallest key in the sequence. Such a key will be denoted as select(i; X). These two important comparison problems have been studied extensively by computer scientists. Both sorting and selection have asymptotically optimal sequential algorithms. There are several sorting algorithms that run in time O(n log n) in the worst case (see e.g., [1]). The problem of sele...