You can put multiple conditions in the sort, using the || operator, so that when the first rule is equal (ie, =0), the second rule will kick in, otherwise take the first rule.
$strings{"E1,E2"} = 1;
$strings{"E1,E3"} = 3;
$strings{"E1,E4"} = 2;
$strings{"E1,E5"} = 3;
$strings{"E1,E6"} = 3;
$strings{"E1,E7"} = 5;
$strings{"E1,E8"} = 1;
$strings{"E1,E9"} = 0;
$strings{"E1,E10"} = 12;
my @sorted =
map { $_->[0] }
sort { ($b->[2] <=> $a->[2]) || ($a->[1] <=> $b->[1]) }
map {
my $old_key = $_;
# transform my keys so I can compare them as digits
my ($k1, $k2) = $old_key =~ /(\d)/g;
my $new_key = sprintf("%04d%04d", $k1, $k2);
[ $old_key, $new_key, $strings{$old_key} ]
} keys %strings;
print map{ "$_ = $strings{$_}\n" } @sorted;