my @sorted = sort { $person{firstname}[$a] cmp $person{firstname}[$b] }
             0 .. $#{ $person{firstname} };

foreach (keys %person) {
   @{ $person{$_} } = @{ $person{$_} }[@sorted];
}

foreach (0 .. $#{ $person{firstname} }) {
   print("firstname: ", $person{firstname}[$_], "\n");
   print("lastname:  ", $person{lastname }[$_], "\n");
   print("city:      ", $person{city     }[$_], "\n");
   print("\n");
}