How to use std::sort() when my binary predicate is NOT transitive?

Hi all,

It seems that std::sort() is using algorithm like quick sort to do the
comparison, that means, the items to be sorted are not pair-wisely
compared. Thus, if the binary predicate is NOT transitive, then the
std::sort() may not work well.

For example, I have a list of nodes, each node has a list of node
references to its immediate children. I want to sort the list so that a
child must appear before its parent.

Since in my data structure, I only know the immediate children of each
node, thus my predicate can only tell whether node1 is an immediate
child of node2.
    bool IsChild(const Node& n1, const Node& n2)
    {
        return std::find(n2.children.begin(), n2.children.end(), &n1) !=
               n2.children.end();
    }

    std::sort(nodes.begin(), nodes.end(), IsChild);

Its possible that node1 is child of node2, node2 is child of node3, so
the expected sorting result should be: {node1, node2, node3}. However,
if it happens that std::sort() calls IsChild() to compare node1 and
node3, it cannot find immediate relationship thus returns "not a child",
and that lead to wrong sorting result. Some prototyped testing proved
such wrong result.

I'm thinking about this problem but I could not find an easy solution
with minimal change on the Node data structure. Does anyone have any
idea about how to solve this problem? Any suggestions are greatly
appreciated!

Best regards,
Chen Zhuo