While it does increase your complexity, I fail to see why hash flattening or restructuring will not accomplish your goal - the solutions presented here are certainly applicable to your scenario:

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

my %sorthash = ();

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

# Flatten
my @flat_array = ();
for my $key1 (keys %sorthash) {
    for my $key2 (keys %{$sorthash{$key1}} ) {
        for my $key3 (keys %{$sorthash{$key1}{$key2}} ) {
            for my $key4 (keys %{$sorthash{$key1}{$key2}{$key3}} ) {
                for my $key5 (keys %{$sorthash{$key1}{$key2}{$key3}{$k
+ey4}} ) {
                    push @flat_array, [$key1, $key2, $key3, $key4, $ke
+y5, $sorthash{$key1}{$key2}{$key3}{$key4}{$key5}];
                }
            }
        }
    }
}

# Sort flat array
for my $entry (sort { $a->[3] <=> $b->[3] or $a->[2] <=> $b->[2] } @fl
+at_array)
 {
    print join ", ", @$entry;
    print "\n";
}
[download]

If that's getting a little deep in terms of nested loops, you can write a recursive crawler to flatten the list:

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

my %sorthash = ();

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

# Flatten
my @flat_array = hash_crawler(\%sorthash);

# Sort flat array
for my $entry (sort { $a->[3] <=> $b->[3] or $a->[2] <=> $b->[2] } @fl
+at_array)
 {
    print join ", ", @$entry;
    print "\n";
}

sub hash_crawler {
    my ($value, @prefix_array) = @_;
    my @results = ();
    if (ref $value) {
        for (keys %$value) {
            push @results, hash_crawler($value->{$_},@prefix_array,$_)
+;
        }
    } else {
        push @results, [@prefix_array, $value];
    }
    return @results;
}
[download]

Update: Fixed bug as per rubasov's post below.