2024/04/06 by Haeupler, Bernhard, Hladík, Richard, Iacono, John +3 · 6 citations
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.2404.04552
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(\lg T) on the number of comparisons has a time bound of O(n2.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.