Nicely done dingus. I'd offer one tweak. I assume that the OP wanted to print just the current record to the "sorted" file and not the whole file from the seek offset:

for my $zipCode (sort{ $a <=> $b }(keys(%zips))) {
   for my $offset (@{$zips{$zipCode}}) {
      seek FILE, $offset, 0;
      while (<FILE>) {
         last unless (/Zip:$zipCode/);
         print SORTED $_;
      }
   }
}
[download]

-- vek --