I think this will do what you want:

@sorted = sort { $hashed{$a} <=> $hashed{$b}
                 || $a cmp $b } keys %hashed;
[download]

The string comparison on keys only happens when the hash's values are equal, because of the short-circuit behavior of ||.

After Compline,
Zaxo