I think you're running into difficulty because you're conflating 'sorting' with what we would call a total or linear ordering. Partial orders are non-linear, and allow you to form posets, which are isomorphic with DAGs. Then you have the broader family of orderings containing weak orders, preorders, strictness, etc. which make matters more complicated. Cyclic orders drop transitivity, for example, allowing you to describe directed graphs with cycles. The thing is that sorting also isn't strictly about orderings. It also encapsulates classification, which are a family of operations entirely distinct from order. There's overlap in the structural implications of some orderings and classifications, but they're also distinct categories (and both are important in ML.)