Answers are grounded in this paper and cite their sources.
We study the generalized sorting problem where only a subset of the pairs can be compared. Equivalently, we are given an n-vertex m-edge graph $G=(V, E)$ where the vertex set V is to be sorted, and the edge set E indicates possible comparisons. The goal is to sort V with as few (adaptive) queries to E as possible. When G is the complete graph, the problem is equivalent to standard sorting for which Θ(n log n) queries are sufficient and necessary. All classical sorting algorithms crucially rely on the ability to compare any pair and do not imply an o(n²)-query algorithm in the general case. This was improved 15 years ago by Huang, Kannan, and Khanna [FOCS'11] who achieved a bound of O(n√n). Kuszmaul and Narayanan [FOCS'21] later gave a bound of O(√m n), which is more efficient for sparse graphs, but matches the O(n√n) barrier for dense graphs. In this paper, we present an algorithm for generalized sorting that makes at most O(n4/3) queries, therefore breaking the longstanding O(n√n) barrier for all graphs. The key to our result is to query edges that belong to many (specific types of) four-cycles. We show that querying such edges allows the algorithm to verify the direction of many other edges (specifically, their opposing edges in the four-cycles) and thus achieve a much better amortized query cost.
No takes yet. Share an insight, caveat, or question.
Behnezhad et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: