I'm not familiar with the module, but the logical short circuit OR operator can help here.

Assume you have a hash as you've described above, called %people:

my @sortedkeys = sort { $people{$a}->[0] cmp $people{$b}->[0] or
                        $people{$a}->[1] cmp $people{$b}->[1] or
                        $people{$a}->[2] cmp $people{$b}->[2]    }
    keys %people;
[download]