You could also use a Schwartzian Transform-like approach, in which you massage your data into a list of first-level,second-level key pairs, which you then sort by index [1] (the second-level key). This also allows to have multiple second-level entries per first-level key.  The first-level key is available in [0], so you can easily reconstruct all data for output:

#!/usr/bin/perl

use strict;
use warnings;

my %sorthash;

$sorthash{10}{20} = 3;
$sorthash{10}{40} = 1;
$sorthash{40}{50} = 4;
$sorthash{20}{30} = 2;

print 
  map { "keys: $_->[0]\t$_->[1]\tvalues: $sorthash{$_->[0]}{$_->[1]}\n
+" }
  sort { $a->[1] <=> $b->[1] }
  map { my $key=$_; map { [$key, $_] } keys %{$sorthash{$key}} }
  keys %sorthash;

__END__
keys: 10    20    values: 3
keys: 20    30    values: 2
keys: 10    40    values: 1
keys: 40    50    values: 4
[download]

Update: note that the approach can in principle be extended to more than two levels. Just create the appropriate [$key1, $key2, $key3, ...] entries (think of spreadsheet-like rows) and sort by whatever column you want.