Another approach: (untested code follows)

my @objects;
while (<FILE>) {
  my ($location,$time) = /^..(.{9})(.{4})/;
  push @objects, bless [
    $location,
    $time,
    $location.$time,
    tell(FILE)
  ], MyObject;
}
package MyObject;
sub overload cmp => sub { $_[0]->[2] cmp $_[1]->[2] };
sub location { return shift->[0] }
sub time { return shift->[1] }
sub record { seek FILE,shift->[3],0; my $b; read FILE,$b,80; return $b
+ }
[download]

The overload would allow plain old sort to work on the array, and should be pretty fast as the keys to sort on are stored already.

The time conversion could possible by done by a function which stores previously converted values in a hash, so you can do a cheap hash lookup instead of an expensive conversion for values you've already seen.

You'll need to make sure the filehandle stays open, possibly in the MyObject package so the records can be retreived when they're actually needed</P.