Answers are grounded in this paper and cite their sources.
We continue the study of the classic generalized sorting problem, a basic variant of ordinary sorting. There are n elements and an (initially hidden) total ordering $π$ over them. Unlike in ordinary sorting, however, only some comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, Θ(n log n) comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been Õ(n3/2) since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require n1+Ω(1) comparisons. We show that it does not: we give a randomized algorithm that uses O(n log⁴ n) comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.
No takes yet. Share an insight, caveat, or question.
Khanna et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: