Sorting Using Partial Information - Robert Tarjan

Computer Science/Discrete Mathematics Seminar I
Topic: Sorting Using Partial Information
Speaker: Robert Tarjan
Affiliation: Princeton University
Date: September 30, 2024
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.