# Given a list of comparisons, sort items with as few additional comparisons as possible

You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons c[0], ..., c[k] for those items (e.g. c[0] = (x[0] < x[4]), c[1] = (x[3] > x[7]), 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.

• Are you looking for a practical implementation or just a theoretical one like the current answer? Apr 3, 2022 at 23:08
• @SalvatoreAmbulando a practical implementation would be nice, but I was mostly interested in the theory Apr 4, 2022 at 5:35
• This paper talks about the problem and gives what they say is a more practical solution. I found it a bit easier to understand too. arxiv.org/abs/0911.0086 I didn't know this was a question people were specifically studying before I saw your question, thanks! Apr 4, 2022 at 15:28