algorithm - Sorting given pairwise orderings -

i have n variables (var 1 ... var n) , not know exact values. n choose 2 pairwise ordering between these n variables known. instance, known var 5 <= var 9, var 9 <= var 10 , on pairs. further, known these pairwise orderings consistent , not lead degenerate case of equality throughout. is, in above example inequality var 10 <= var 5 not present.

what efficient sorting algorithm such problems gives sorting of variables?

the question not how sort (use standard sort of language) how feed sort criterion sorting algorithm.

in languages need provide int comparison (t a, t b) t type of elements, returns -1, 0 or 1 depending on larger.

so need fast access data structure storing (all) pairwise orderings, given pair of elements.

so question not var 10 <= var 5 present (inconsistent) more var 5 <= var 10 ensured present ? if case, can test presence of constraint in o(1) hash set of pairs of elements, otherwise, need find transitive relationship between , b, might not exist (it's unclear op if talking of partial or total order, i.e. a,b ensure < b or b < or = b (total order).

with worst case n^2 entries, hash pretty big. building still requires exploring transitive links costly.

following links means map of elements sets of (immediately) smaller elements, when comparing b, if (map(a) contains b) or (map(b) contains a) can answer immediately, otherwise need recurse on elements of map(a) , map(b), pretty bad complexity. you'll still cumulating sets of smaller values build test.

perhaps if have low number of constraints a <= b, applying permutation of , b when not respect constraint , iterating on constraints fixpoint (all constraints applied in 1 full round no effect) more efficient. @ least it's o(1) in memory.

a variant of sorting using stable sort (preserves order of incomparable entries) several times subsets of constraints.

last idea, computing max input data o(number of constraints), repeatedly compute max, add @ end of target, remove constraints use it, rinse , repeat. i'd use stack store largest element given constraint index, can backtrack rather restart scratch.