Fast and Simple Sorting Using Partial Information

Bernhard Haeupler, Richard Hladík, John Iacono +3

We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T…