Distinguished Lecture: Fast and Simple Sorting Using Partial Information

Abstract: 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 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 which has been open since 1978 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of O(log T) on the number of comparisons has a non-linear time bound and is much more complicated. 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 Iacono, Václav Rozhoň, and Jakub Tětek.

Bio: Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He has held academic and industrial positions at prestigious institutions including Cornell, Berkeley, Stanford, and NYU, as well as at Bell Labs, NEC, HP, Microsoft, and Intertrust Technologies. Noted for his groundbreaking work in data structures and graph algorithms, Tarjan has received numerous accolades including the Nevanlinna Prize in 1982, the Turing Award in 1986, and the Paris Kanellakis Award in 1999. He is a member of several esteemed academies and has authored over 200 publications and holds 38 U.S. patents.