If you really want the original lines (i.e. if that's your output), and you don't want to separate them into columns later, then you can use this:

#!/usr/bin/perl -w
use strict;
my @original = <>; # or whatever.
my @lines =
  map { $_->[0] }
  sort { $a->[1] <=> $b->[1] or $a->[2] <=> $b->[2] }
  map { [ $_, unpack('x12a9xa12', $_) ] }
  @original;
[download]

This is the Schwartzian Transform, with the use of unpack to undo the fixed fields. unpack() is more efficient than multiple substr() calls. Of course, if you want also to unpack the columns, you can simplify it:

#!/usr/bin/perl -w
use strict;
my @original = <>; # or whatever.
my @lines =
  sort { $a->[0] <=> $b->[0] or $a->[1] <=> $b->[1] }
  map { [ unpack('x12a9xa12', $_) ] }
  @original;
[download]

This leaves you with an array of array references, with the fields already separated. Of course, you'd change the unpack string and array indices to include the data you were interested in.

Anyway, if you're dealing with fixed-field data, I'd recommend looking at unpack to separate the fields.