list - Is a partially ordered sort possible without using a tree? -

list - Is a partially ordered sort possible without using a tree? -

background:

so have few hundred elements (image simple case) need re-sort since sorting value changes whenever elements x or y value changes. normal (absolute) sort not possible since many elements have undefined relation each other (like violet , orange block) break merge/quick/bubble-sort. however, changing single element can potentially alter many ordering relationships if element had border many others (like if greenish block removed)

i understand thought behind building tree , doing topological sort seems horribly inefficient time because of single element changing.

if above still unclear, check out http://shaunlebron.com/isometricblocks since similar trying do.

my question: can't help think tree not necessary (at to the lowest degree case) linked list fine, since case guarantees there never cycle. wouldn't sufficient (with ascending order) place element after lastly element greater than, before first element less than? wouldn't allow sorting of partially ordered set?

is there case prevents person skipping tree step , going straight list? every simulation i've done on paper seems suggest work.

simply put, yes, partially ordered sort possible without using tree.

if have (original) unsorted list "u" , (empty, destination) sorted list "s", need loop on list "u" , move entries have no dependents remaining end list "s".

an entry has no dependents remaining if no other entry in list "u" dependent upon it. if using {-1, 0, 1} measure equality, need pick either "-1" or "1" imply dependency. whereas "0" imply there no valid ordering 2 elements.

list sorting tree order topological-sort