1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.