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 x1, x2, ..., xn such that if xi ≤ xj, i ≤ j?
There's a paper titled Sorting and Selection in Posets 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.