How can I sort a Perl hash on values and order the keys correspondingly (in two arrays maybe)?

First sort the keys by the associated value. Then get the values (e.g. by using a hash slice).

my @keys = sort { $h{$a} <=> $h{$b} } keys(%h);
my @vals = @h{@keys};

Or if you have a hash reference.

my @keys = sort { $h->{$a} <=> $h->{$b} } keys(%$h);
my @vals = @{$h}{@keys};