Sort hierarchically related data together

Question

I have a list of items of Type A and they are heirarchially related items like below

Actual

List[
A{id:1,parentId:1}
A{id:2,parentId:1}
A{id:3,parentId:1}
A{id:4,parentId:1}
A{id:6,parentId:2}
A{id:7,parentId:6}
]

I need to sort it in the following way. I tried my hands on comparator, but it does gets complicated. I'm not sure if I have to go with treesort or any other algorithm to solve this issue. Thanks.

Required

List[
A{id:1,parentId:1}
A{id:2,parentId:1}
A{id:6,parentId:2}    
A{id:7,parentId:6}
A{id:3,parentId:1}
A{id:4,parentId:1}
]

As you can see that the hierarchical items are all sorted to the beginning(need not be in the beginning) but have to be together within the list.

Answer 1

Updated
You should use depth-search algorithm, like described here.
This image illustrates the idea of how to get order you need:

In pseudo-code it's simple, here is sort version of depth-search algorithm:

_items[] depthSort (_parent){
  add _parent to _items[];

  get _children of _parent sorted by desired attribute;

  for every _item in _children
      depthSort(_item);
}

Answer 2

I am a bit confused. You say you want it sorted with the hierarchy (parentIds) grouped. But your Required output has your "parentId:1" group split into two?

If you want the parents grouped, then you have a bug in your desired output.

--- Update ---

Ok, so you don't want your sort grouped by the parents, you want it to be a depth first sort.

recursiveDepthFirstWalk(List<Node> sorted, Node parent);
  if (parent != null) {
    sorted.add(parent);
  }
  List<Node> children = parent.getChildren();
  sort(children);
  for (Child child : children) {
    recursiveDepthFirstPrint(sorted, child);
  }
}

Note that there are much better implementations of this idea available.