I don't think it's possible using just the builtin sort commmand. What about:

# First, sort @arr1.
@arr1 = sort {
   my ($c) = $a =~ /:::(\d+)$/;
   my ($d) = $b =~ /:::(\d+)$/;
   +$c <=> +$d
} @arr1;

# Then recreate @arr2.
@arr2 = map { s/^.*:::(\d+)$/$1/ } @arr1;
[download]

or:

@arr3 = sort { $a->[1] <=> $b->[1] }
   map { [ $arr1[$_], $arr2[$_] ] }
      (0..$#arr1);
@arr1 = map { $_->[0] } @arr3;
@arr2 = map { $_->[1] } @arr3;
[download]