On generalized comparison-based sorting problems

We survey recent results on comparison-based sorting problems involving partial orders. In particular, we outline recent algorithms for partial order production and sorting under partial information. We emphasize the complementarity of the two problems and the common aspects of the algorithms. We also include open questions on two other related problems, namely partial order identification and sorting with forbidden comparisons. © Springer-Verlag 2013.SCOPUS: cp.k