Sorting Using Partial Information

We consider the problem of sorting a set of items having an unknown total order by doing binary comparisons of the items, given the outcomes of some pre-existing comparisons. We present a simple new algorithm with a running time of O(m + n + log T), where n, m, and T are the number of items, the number of pre-existing comparisons, and the number of total orders consistent with the outcomes of the pre-existing comparisons, respectively. The algorithm does O(log T) comparisons. Both our time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been open since 1978. Our algorithm combines two classic algorithms: topological sort and heapsort with the right kind of heap.

This is joint work with Bernhard Haeupler, Richard Hladík, John lacono, Vaclay Rozhoi, and Jakub Tětek.