#!usr/bin/perl
use strict;
use warnings;

my %hash1 = (
    '1' => 1,
    '2' => 1,
    '3' => 1,
    '4' => 1,
    '5' => 1,
);

my %hash2 = (
    '1' => {'key' => 'a'},
    '2' => {'key' => 'b'},
    '3' => {'key' => 'a'},
    '4' => {'key' => 'a'},
    '5' => {'key' => 'b'},
    );

foreach my $key1 (
    sort { $hash2{$a}{'key'} cmp $hash2{$b}{'key'} || $a <=> $b } keys %hash1) {
    print "key $key1 and $hash2{$key1}{key}\n";
}

__END__

$ perl test.pl
key 1 and a
key 3 and a
key 4 and a
key 2 and b
key 5 and b
$ perl test.pl
key 1 and a
key 3 and a
key 4 and a
key 2 and b
key 5 and b
$ perl test.pl
key 1 and a
key 3 and a
key 4 and a
key 2 and b
key 5 and b
$ perl test.pl
key 1 and a
key 3 and a
key 4 and a
key 2 and b
key 5 and b