Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them
The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging.

Kahn and Saks showed that partially sorted lists can be sorted in $O(\log M)$, where $M$ is the number of possible orderings consistent with the partial order. I'm not sure that their algorithm is efficient, though. The best constant in the big O is the subject of the 1/3–2/3 conjecture.