Stochastic and Worst-Case Generalized Sorting Revisited

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.

I. Introduction

Whereas the standard comparison-based sorting problem was solved more than half a century ago, several variations on the problem have only recently begun to be understood. One of the most natural of these is the so-called generalized sorting problem.