Fast and Simple Sorting Using Partial Information
<|reference_start|>Fast and Simple Sorting Using Partial Information: We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple, 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.   Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $O(\lg T)$ on the number of comparisons has a time bound of $O(n^{2.5})$ and is more complicated. (A recent independent and concurrent work by Van der Hoog and Rutschmann implies an $O(n^{2.371552})$-time algorithm with $O(\log T)$ comparisons.)   Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient insertion into a sorted list. It outputs the items in sorted order one by one. As a result, it can be modified to solve the important and more general top-$k$ sorting problem: Given $k$ and the outcomes of some pre-existing comparisons, output the smallest $k$ items in sorted order. The modified algorithm solves the top-$k$ sorting problem in minimum time and comparisons, to within constant factors.<|reference_end|>
@article{haeupler2024fast,
    title={Fast and Simple Sorting Using Partial Information},
    author={Bernhard Haeupler, Richard Hlad'ik, John Iacono, Vaclav Rozhon,
  Robert Tarjan, Jakub Tv{e}tek},
    journal={arXiv preprint arXiv:2404.04552},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.04552},
    primaryClass={cs.DS}
}