nothingmuch, although the OP said this works, it didn't work for me.

UPDATE: it was a typo. I think nothingmuch meant

my $sorted = [ sort {
    $a->{under} <=> $b->{under}
    || $a->{order} <=> $b->{order}
} @$aoh ];
[download]