sort { $hoa{$a}->[0] cmp $hoa{$b}->[0] } keys %hoa;
[download]

Update: An expanded answer:

my @sorted_keys = sort { $hoa{$a}->[0] cmp $hoa{$b}->[0] } keys %hoa;
foreach my $row_key ( @sorted_keys ) {
    print "<tr><td>$row_key:</td>\n";
    my $index = 0;
    foreach my $cell ( @{ $hoa{$row_key} } ) {
        print "<td>$index = $cell</td>";
        $index++;
    }
    print "</tr>\n";
}
[download]

This sorts the rows by the first element of the arrays within the rows.