I'm going to go out on a limb and say that your sort is just fine - it's your map that's the problem. Instead of

map { 
    if ( m/^(.+?)\((\d+)\)\s-\s\[(.+?)\].+?"(.*?)"\.$/ )
    {
        my ($disc_file,$page,$key,$val) = ($1,$2,$3,$4);
        [$_,$disc_file,$page,$key];
    }
}
[download]

Maybe try something like:

map {
    m/^(.+?)\((\d+)\)\s-\s\[(.+?)\]/
        ? [$_,$1, $2, $3]
        : ()
}
[download]

The big thing is that you're doing unnecessary matches and variable creation/assignments. map is naturally more obfuscated than other operations. If you want to de-obfuscate it, consider changing to a multi-operation sequence.

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.