  The \emph{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, \dots, 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\H{o}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 \log (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.
