Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

Question

Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs?

Example 1: set(a, b, c, d, e) pairs(a>b, ce)

Example 2: set(a, b, c, d, e) pairs(a>b, d>b, c>d, d>e)

• D.W.: I don't understand what "pairs(a>b, ce)" is supposed to mean. But perhaps look at en.wikipedia.org/wiki/Topological_sorting.

Answer 1

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.