Is a partially ordered sort possible without using a tree?

Background: Mid sized example

So I have a few hundred elements (image is a simple case) that I need to constantly re-sort since their sorting value changes whenever the elements X or Y value changes. A normal (absolute) sort is not possible since many elements have an undefined relation to each other (like the purple and orange block) that would just break a merge/quick/bubble-sort. However, changing a single element can potentially change many ordering relationships if that element had an edge to many others (like if the green block were removed)

I understand the idea behind building a tree and doing a topological sort but this seems horribly inefficient to do all the time because of a single element changing.

If the above is still unclear, check out http://shaunlebron.com/IsometricBlocks since that is fairly similar to what I am trying to do.

My question: I can't help but think that a tree is not necessary (at least for my case) but that a linked list would be fine, since my case guarantees that there will never be a cycle. Wouldn't it be sufficient (with ascending order) to just always place an element after the last element that it is greater than, but before the first element that it is less than? Wouldn't this effectively allow sorting of a partially ordered set?

One valid absolute ordering of the elements

Is there some case that prevents a person from just skipping the tree step and going straight to a list? Every simulation I've done on paper seems to suggest that this would work.

Solution

Simply put, yes, a partially ordered sort is possible without using a tree.

If you have your (original) unsorted list "U" and (empty, destination) sorted list "S", you will need to loop over list "U" and move entries which have no dependents remaining to the end list "S".

An entry has no dependents remaining if no other entry in list "U" is dependent upon it. If you are using {-1, 0, 1} to measure equality, then you will need to pick either "-1" or "1" to imply dependency. Whereas "0" would imply that there is no valid ordering for the two elements.