Fast and Simple Sorting Using Partial Information
This resolves a fundamental problem in comparison-based sorting with partial information, providing optimal time and comparison bounds for both full sorting and top-k sorting.
The paper presents a deterministic algorithm for sorting n items given m pre-existing comparisons, achieving O(m + log T) time and O(log T) comparisons, where T is the number of consistent total orders. These bounds are optimal up to constant factors, resolving a long-standing open problem since 1976.
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. 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(\log T)$ on the number of comparisons has a time bound of $O(n^{2.5})$ and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving 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.