The fundamental problem (as noted in other threads) is that we only have a partial ordering on the set, i.e. some pairs of nodes don't satisfy (a <= b or a => b). My sort comparator returns equal for such pairs (e.g. two root nodes) which breaks the sorting algo, as you noted.

perldoc -f sort says: "The comparison function is required to behave. If it returns inconsistent results (sometimes saying $x1 is less than $x2 and sometimes saying the opposite, for example) the results are not well-defined." My comparator was badly-behaved for different reason. It doesn't satisfy transitivity: i.e. a == b && b == c does not imply a == c.

As well as CPAN's Graph module, there is slightly more direct Sort::Topological which appears to do the job (in essentially the same way the other code posted appears to do it - associate a depth and sort on that).

(Side note: if testing other approaches, note that your example list is already sorted - the first three elts are all root nodes). In the code below, I've reversed the dependency, so that the fourth depends on the second.)

#!/usr/bin/perl
use strict;
use warnings;
use Sort::Topological qw/toposort/;
use Class::Struct Item => {
    id => '$',
    deps => '@',
};

my @items;
push @items, Item->new(id =>  $_) for 1..4;
# Make $items[1] a rank 'deeper', so it should sort last
$items[3]->deps([$items[1]]);

map { print "id: ", $_->id, "\n" } @items;
# 1, 2, 3, 4
@items = toposort(sub { my $i = shift; @{$i->deps}; }, \@items);
map { print "id: ", $_->id, "\n" } @items;
# 1, 3, 4, 2
[download]