Optimal randomized algorithms for local sorting and set-maxima
Wayne Goddard, Valerie Jean King, Leonard J. Schulman · 1990
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 in 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.