How about extending it to something like

pack("n N n", $1, $2, $3).$4

thereby we would sort CD# > 9 correctly, decrease the memory footprint and allow for the fast intrinsic ASCIIbetical sort.
Perhaps even to the point where fast hash lookups can be used.

It's a pity the data is in practice unavailable

Here's what I would like to time ...

.
.
my (%sort_hash);
my $offset = 0;
while (<IN>) {
    if(  m/^CD(\d+)\\(\d+)\.pdf\((\d+)\)\s-\s\[(.+?)\]/  ) {
        $sort_hash{pack("n N n", $1, $2, $3).$4} = $offset;
    } 
    $offset = tell(IN);
}

foreach my $k (sort keys %sort_hash) {
   seek IN, $sort_hash{$k}, 0;
   print OUT scalar(<IN>);
}
[download]