Just flatten the list first (formatting the items so they sort properly), sort, then reformat how you would like to output them (which isn't even required in this case):

my %HoA = ( 
        simpsons    => [ "homer", "marge", "bart" ], 
        flintstones => [ "fred", "barney" ], 
        jetsons     => [ "george", "jane", "elroy", "astro" ], 
); 

my @members= sort map {
    my $key= $_;
    map " $_ : $key", @{$HoA{$key}};
} keys %HoA;

print join $/, @members, "";
__END__
[download]

Produces:

 astro : jetsons
 barney : flintstones
 bart : simpsons
 elroy : jetsons
 fred : flintstones
 george : jetsons
 homer : simpsons
 jane : jetsons
 marge : simpsons
[download]

                - tye