Need help with algorithm for sorting list

The answer is probably obvious but not to me at this moment, so I was wondering if somebody who is better with sorting algorithms can help lead me in the right direction. This is not homework, I am legitimately trying to work within an existing design for something work related.

Essentially I start with an unordered list of data objects that represent something similar to forum comments. These objects MAY explicitly have one and only one direct parent. In other words

Parent (1...*) ----------- (1...1) Child

A child has a reference to its parent, however a parent cannot see its children (explicitly).

Typically when sorting a list one would pass a comparator which given any two data objects in the collection should return an integer number that represents the distance between the two objects in a graph. The distance between two completely unrelated comments will be based on the Timestamp value of the data object.

The issue is that any two data objects can and should only be compared by timestamp with other data objects from the same parent branch. Here is an example:

DO1 - Time(1000ms)

|___DO3 - Time(5000ms)

DO2 - Time(2000ms)

DO1 and DO2 compared will result in a negative number so those two are sorted correctly relative to each other. DO3 to DO1 is likewise correct because I can assume that any branch above a comment must be less than. The problem comes with comparing DO3 to DO2. I thought that I should compare the highest order parent to DO2 in this case and that works until there are DO children under DO3.

I am trying to figure out if the current object graph is even enough information for a comparator to correctly return an appropriate number for any two comparisons. Perhaps the comparator needs to be initialized with the unordered list first so that it can build a tree structure where I can see a list of children from any given parent explicitly? Or perhaps I need to refactor? At this stage I am not concerned about performance. Thank you.

The obvious approach is to walk the tree depth first, taking children of each node in order of their timestamp. That is the order you want.

Building the tree and than iterating it will obviously save you time, but you can just take all entries with given parent pointer while testing.

Alternatively you could define the ordering so that descendants come after their predecessors and other nodes are ordered by timestam of immediate children of their common ancestor. So:

``````ROOT
+- DO1 T=1
|   +- DO2 T=5
|   +- DO3 T=8
|       +- DO4 T=12
+- DO5 T=3
+- DO6 T=11
``````

`DO2 > DO1` because it's a descendant, `DO4 >`DO1`because it's also descendant,`DO3`>`DO2`because they are both immediate children to their ancestor`DO1`and`DO3`has higher timestamp and`DO6`>`DO4`because their ancestor is`ROOT`to which you come from`DO6`via`DO5`and from`DO4`via`DO1`and`DO5`has higher timestamp than`DO1`.

But building and walking the tree is going to be faster.

• "Depth first" means that the parents will have to know their children - seems that is what the OP is trying to avoid. And your second approach needs to have a method for finding the common ancestor of any two nodes, but you did not write anything how to do this programmatically, so IMHO it does not give an answer to the original question. Feb 3, 2012 at 13:56
• @JanHudec and DocBrown, Regardless, this answer gave me a lot to think about and set me off in the right direction. I found a some quick and dirty Tree and Node classes online that take order branches with a comparator. I am currently playing with that so I can build a tree and then just walk it to find out how far any one object is from another in my higher order comparator. The only drawback is that everytime I insert a new object into the unordered list, I need to rebuild the tree. Such is life, premature optimization is the root of all evils. Feb 3, 2012 at 14:58
• @maple_shaft: Well, you don't have to rebuild the tree when an item is added, you only need to insert the new item into it. Feb 6, 2012 at 7:45