Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps

Abstract

In 1972, Fredman proposes the problem of sorting under partial information: preprocess a directed acyclic graph $G$ with vertex set $X$ so that you can sort $X$ in $O(\log e(G))$ time, where $e(G)$ is the number of sorted orders compatible with $G$. Cardinal, Fiorini, Joret, Jungers and Munro [STOC'10] show that you can preprocess $G$ in $O(n^{2.5})$ time and then sort $X$ in $O(\log e(G)+n)$ time and $O(\log e(G))$ comparisons. Recent work of van der Hoog and Rutschmann [FOCS'24] implies an algorithm with $O(n^{\omega })$ preprocessing time where $\omega <2.372$ and $O(\log e(G))$ sorting time. Haeupler, Hladík, Iacono, Rozhoň, Tarjan and Tětek [SODA'25] achieve an overall running time of $O(\log e(G)+m)$. In this paper, we achieve tight bounds for this problem: $O(m)$ preprocessing time and $O(\log e(G))$ sorting time. As a key ingredient, we design a new fast heap data structure that might be of independent theoretical interest. Our heap satisfies the unified bound, which has previously been studied for dictionaries and binary search trees.

arXiv commentTo appear at FOCS 2026