What is the best way to sort a partially ordered list?

Question

Probably best illustrated with a small example.
Given the relations

A < B < C
A < P < Q 

Correct outputs would be

ABCPQ or APQBC or APBCQ ... etc.

In other words, any ordering is valid in which the given relationships hold.

I am most interested in the solution that is easiest to implement, but the best O(n) in speed and time is interesting as well.

Answer 1

This is called topological sorting.

The standard algorithm is to output a minimal element, then remove it and repeat until done.

Answer 2

Do several sorts. First sort according to the first rule, then according to the second one and so on. Should work, unless your rules contain contradictions. sure easy enough to implement.