<p>There's a paper titled <a href="http://arxiv.org/abs/0707.1532v1" rel="noreferrer" title="Sorting and Selection in Posets">Sorting and Selection in Posets</a> available on arxiv.org which discusses sorting methods of order O((w^2)nlog(n/w)), where w is the "width" of the poset.  I haven't read the paper, but it seems like it covers what you are looking for.</p>
Sorting a poset?
<p>There are a huge number of sorting algorithms out there, but most of them only work on totally-ordered sets because they assume that any two elements are comparable.  However, are there any good algorithms out there for sorting posets, where some elements are uncomparable?  That is, given a set S of elements drawn from a poset, what is the best way to output an ordering x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub> such that if x<sub>i</sub> &le; x<sub>j</sub>, i &le; j?</p>