  In this paper we study the problem of sorting under non-uniform comparison
costs, where costs are either 1 or $\infty$. If comparing a pair has an
associated cost of $\infty$ then we say that such a pair cannot be compared
(forbidden pairs). Along with the set of elements $V$ the input to our problem
is a graph $G(V, E)$, whose edges represents the pairs that we can compare
incurring an unit of cost. Given a graph with $n$ vertices and $q$ forbidden
edges we propose the first non-trivial deterministic algorithm which makes
$O((q + n)\log{n})$ comparisons with a total complexity of $O(n^2 +
q^{\omega/2})$, where $\omega$ is the exponent in the complexity of matrix
multiplication. We also propose a simple randomized algorithm for the problem
which makes $\widetilde{O}(n^2/\sqrt{q + n} + n\sqrt{q})$ probes with high
probability. When the input graph is random we show that
$\widetilde{O}(\min{(n^{3/2}, pn^2)})$ probes suffice, where $p$ is the edge
probability.
