  We consider the problem of partial order production: arrange the elements of
an unknown totally ordered set T into a target partially ordered set S, by
comparing a minimum number of pairs in T. Special cases include sorting by
comparisons, selection, multiple selection, and heap construction.
  We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the
worst case. Here, n denotes the size of the ground sets, and ITLB denotes a
natural information-theoretic lower bound on the number of comparisons needed
to produce the target partial order.
  Our approach is to replace the target partial order by a weak order (that is,
a partial order with a layered structure) extending it, without increasing the
information theoretic lower bound too much. We then solve the problem by
applying an efficient multiple selection algorithm. The overall complexity of
our algorithm is polynomial. This answers a question of Yao (SIAM J. Comput.
18, 1989).
  We base our analysis on the entropy of the target partial order, a quantity
that can be efficiently computed and provides a good estimate of the
information-theoretic lower bound.
