# untested ...

use Encode qw(encode decode);
use MIME::Base64 qw(encode_base64);

my $tempfn = "sort.temp"; # better use File::Temp!
open my $tmp, ">", $tempfn or die ...;

while(<>) {
  my $k0 = encode_base64(encode(cp1047 => substr($_, 3, 17)), "");
  my $k1 = encode_base64("\xff\xff" ^ encode(cp1047 => substr($_, 20, 2)));
  print $tmp join("\0", $k0, $k1, $_);
}

close $tmp or die "...";

open my $sorted, "-|", sort => $tempfn or die "...";
while(<$sorted>) {
  print((split /\x00/, $_, 3)[2]);
}