Fast and Simple Sorting Using Partial Information
Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert Endre Tarjan, Jakub Tětek · Society for Industrial and Applied Mathematics eBooks · 2025
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 ) time and does O(log T ) comparisons, where T is the number of total orders consistent with the pre-existing comparisons.