x, ..., x[n-1]. Beforehand, you're given a list of several comparisons
c, ..., c[k] for those items (e.g.
c = (x < x),
c = (x > x), etc.).
The objective is to sort the items by requesting as few additional comparisons as possible.
For example, if
c contains all the pairwise comparisons, then you don't need to request any additional ones to be able to sort the list. If
c contained nothing, then you'd request
O(n*log(n)) additional comparisons to perhaps quicksort the items. But if
c contained something in between, how could we smartly leverage those existing comparisons to guide the extra comparisons we request?
Computation time doesn't matter (so long as it's sub-exponential). All that matters is the algorithm requests roughly the fewest additional comparisons.
Vaguely, I have an idea about constructing a DAG from the comparisons in
c, and then doing a topological sort for the DAG to get a partial ordering, but I'm not sure where to go from there.