Warning: I'm the person who asked the question!

How I'd do it is

my %hash = (
   foo => 2,
   bar => 1,
   baz => 3,
   bun => 2,
);

my @array = sort {$hash{$a} <=> $hash{$b}} keys %hash;
[download]

Of course, this array only has the hash keys in it, albeit correctly sorted. If you want a data structure with both keys *and* values from %hash then you have to choose a data structure that meets your needs. A straight hash is no good, because you have duplicate values, so you'll lose some key / value pairs when you reverse them. An array of hashes is one choice:

my @array_of_hashes;
push @array_of_hashes, "$hash{$_} => $_\n" for @array;
[download]

And to see what that looks like,

use Data::Dumper;
print Dumper(\@array_of_hashes);
[download]

Gets you

$VAR1 = [
          '1 => bar',
          '2 => bun',
          '2 => foo',
          '3 => baz'
        ];
[download]

... but I'm interested to see what other monks come up with: it was my slight unease with this solution that prompted me to post this question.

Originally posted as a Categorized Answer.