  We generalize the classical nuts and bolts problem to a setting where the
input is a collection of $n$ nuts and $m$ bolts, and there is no promise of any
matching pairs. It is not allowed to compare a nut directly with a nut or a
bolt directly with a bolt, and the goal is to perform the fewest nut-bolt
comparisons to discover the partial order between the nuts and bolts. We term
this problem \emph{bipartite sorting}.
  We show that instances of bipartite sorting of the same size exhibit a wide
range of complexity, and propose to perform a fine-grained analysis for this
problem. We rule out straightforward notions of instance-optimality as being
too stringent, and adopt a \emph{neighborhood-based} definition. Our definition
may be of independent interest as a unifying lens for instance-optimal
algorithms for other static problems existing in literature. This includes
problems like sorting (Estivill-Castro and Woods, ACM Comput. Surv. 1992),
convex hull (Afshani, Barbay and Chan, JACM 2017), adaptive joins (Demaine,
L\'{o}pez-Ortiz and Munro, SODA 2000), and the recent concept of universal
optimality for graphs (Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan and T\v{e}tek,
2023).
  As our main result on bipartite sorting, we give a randomized algorithm that
is within a factor of $O(\log ^3 (n+m))$ of being instance-optimal w.h.p., with
respect to the neighborhood-based definition.
  As our second contribution, we generalize bipartite sorting to DAG sorting,
when the underlying DAG is not necessarily bipartite. As an unexpected
consequence of a simple algorithm for DAG sorting, we rule out a potential
lower bound on the widely-studied problem of \emph{sorting with priced
information}, posed by (Charikar, Fagin, Guruswami, Kleinberg, Raghavan and
Sahai, STOC 2000).
