Here's an approach:

use strict;

my $hoa_ref = {Charlie => [1,2,3,4],
               Andrew  => [9,8,7,6],
               Daniel  => [5,6,2,3]};

for my $key (sort {$hoa_ref->{$a}[0] <=> $hoa_ref->{$b}[0]} keys %$hoa
+_ref) {
   # prove it worded...
   print "$key:";
   for my $item ( @{$hoa_ref->{$key}} ) {
      print " $item";
   }
   print "\n";
}
[download]

Update: Dratted jarich, beat me while I was working it out. ;-)