$i and $j have no meaning (Update: and are given no value; i.e., are uninitialized) in your comparison expression (see sort). Try something like:

foreach my $fn_ln (sort { $statefinal{$a} cmp $statefinal{$b} } keys %
+statefinal) {
  print qq{'$fn_ln' in $statefinal{$fn_ln}};
  }
[download]

Update: NB: This sorts the keys (first/last name) by their values (states) in lexic-ascending order.