# Interactive sort for only top elements

I have a set of objects and a set of comparison results for some of them.

I want an algorithm that returns the next comparison I should make to two objects towards having a way to know the full order of all objects. If the order of all objects can be already known I should get the objects ordered.

Requirements: ask for the minimal number of comparisons between objects as they are the most expensive operation.

For example: I know elements A,B,C,D and relations A->B , A->C , B->D , C->D the algorithm should return next pair to compare B and C

New contributor
Eduardo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Unfortunately no efficient algorithms are known for this problem. Oct 14 at 7:58

A similar question has been considered in the literature: given a poset $$P$$ and a list of elements whose order is consistent with $$P$$, how many comparisons are needed in order to order the list? If there are $$e(P)$$ many extensions of $$P$$ to a linear order, then clearly at least $$\log_2 e(P)$$ many comparisons are needed. Conversely, Kislytsin and Fredman showed (separately) that $$\log_2 e(P) + 2n$$ comparisons suffice, but their algorithms cannot be implemented efficiently. Kahn and Kim gave in their classic paper Entropy and Sorting an efficient algorithm which uses $$O(\log e(P))$$ comparisons.