Stochastic and Worst-Case Generalized Sorting Revisited
William Kuszmaul, Shyam Narayanan · 2022
The generalized sorting problem is a restricted version of standard comparison sorting where we wish to sort$n$elements but only a subset of pairs are allowed to be compared. Formally, there is some known graph$G=(V, E)$on the$n$elements$v_{1, \ldots, v_{n}}$, and the goal is to determine the true order of the elements using as few comparisons as possible, where all comparisons ($v_{i, v_{j}}$) must be edges in$E$. We are promised that if the true ordering is$x_{1 < x_{2} < \cdots < x_{n}}$for$\{x_{i\}}$an unknown permutation of the vertices$\{v_{i\}}$, then$(x_{i, x_{i+1})\in E}$for all$i$: this Hamiltonian path ensures that sorting is actually possible. In this work, we improve the bounds for generalized sorting on both random graphs and worst-case graphs. For Erdős-Renyi random graphs$G(n, p)$(with the promised Hamiltonian path added to ensure sorting is possible), we provide an algorithm for generalized sorting with an expected$O(n\ \text{lg}(np))$comparisons, which we prove to be optimal for query complexity. This strongly improves over the best known algorithm of Huang, Kannan, and Khanna (FOCS 2011), which uses$\tilde{O(\min(n\sqrt{np},\ n/p^{2}))}$comparisons. For arbitrary graphs$G$with$n$vertices and$m$edges (again with the promised Hamiltonian path), we provide an algorithm for generalized sorting with$\tilde{O(\sqrt{mn})}$comparisons. This improves over the best known algorithm of Huang et al., which uses$\min(m,\tilde{O}(n^{3/2}))$comparisons.