Do a GRT through /bin/sort.

# ...
use IPC::Open2 'open2';
my( $chaos, $sorted );
my $pid= open2( $sorted, $chaos, 'sort' );
while(  <>  ) {
    my $ascii= encode( 'cp1047', $_ );
    print $chaos substr($ascii,3,17), substr($ascii,20,2), $_;
}
close $chaos;
while(  <$sorted>  ) {
    print substr( $_, 19 );
}
[download]

or thereabouts. It looks like your EBCDIC file is using ASCII newlines, which simplifies things.