Something like this does the trick. You need another data structure to remember which hash a particular key comes from. You have to use an array as if you use a hash you will stomp on duplicate keys. If you want to sort on the 'D' and 'E' fields as well you would just add the extra sort in the usual way:

$hash{A}{B}{C}{D}{one} = "1";
$hash{A}{B}{C}{D}{two} = "2";
$hash{A}{B}{C}{D}{thr} = "3";

$hash{A}{B}{C}{E}{one} = "4";
$hash{A}{B}{C}{E}{two} = "5";
$hash{A}{B}{C}{E}{thr} = "6";

my @sort;
push @sort, [ $_, 'D' ] for keys %{$hash{A}{B}{C}{D}};
push @sort, [ $_, 'E' ] for keys %{$hash{A}{B}{C}{E}};
for my $ref ( sort { $a->[0] cmp $b->[0] } @sort ) {
    print "Key: $ref->[0]; Hash: $ref->[1]\n";
}
__DATA__
Key: one; Hash: D
Key: one; Hash: E
Key: thr; Hash: D
Key: thr; Hash: E
Key: two; Hash: D
Key: two; Hash: E
[download]

cheers

tachyon

s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print