Optimal Randomized Algorithms for Local Sorting and Set-Maxima

We present randomized algorithms for two sorting problems. In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order of every pair of adjacent vertices. In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set. We describe lower bounds for the problems in the comparison model, and show that the algorithms are optimal within a constant factor. 1. Introduction. In this paper we study two sorting problems. The first is the local sorting problem: given a graph in which each vertex is assigned an element of a total order, one must determine the relative order of every pair of adjacent nodes. This problem restricts to standard sorting when the graph is complete, but in general its complexity depends on the graph selected. The second problem is set-maxima, where the task is to identify the maximum element in each of a collection of sets drawn from a total order. Set-maxima was investigated in (1), (3) and (5). Local sorting appears to be new, although a restricted version was suggested in (6). We present randomized algorithms for these problems and measure their com- plexity in the comparison (decision-tree) model. In that model, one pays only for comparisons between elements of the total order. The algorithms use random bits to help determine which comparisons will be made, but their outcomes must be correct. The complexity of the algorithm is thus the expected number of comparisons made on a worst-case input. We obtain information-theoretic lower bounds for both problems, and show that our algorithms attain these bounds. The output of a local-sorting algorithm is exactly an acyclic orientation of the graph G. Thus an information-theoretic lower bound on the complexity of local sorting, even for randomized algorithms, is given by the logarithm of the number, (G), of acyclic orientations of the graph G. We present an algorithm which is optimal for all graphs—it makes an expected (log(G)) comparisons. We derive an estimate of (G) in terms of the degrees, {dv}, of the vertices {v} of G: specifically log(G) is ( P v∈G log(dv + 1)). Thus the number of comparisons our algorithm makes contrasts with the ( P v∈G dv) comparisons made by the naive algorithm which examines all edges. Closely related to local sorting is the set-sort problem: sort each of a family of possibly overlapping sets. Set-sort is equivalent to locally sorting the graph in which