You should also be able to do a merge sort, holding only the most recently read line of each file in memory.

A quick search found File::MergeSort, which seems what you want. It can sort lines based on a key you specify:

Merge keys are extracted from the input lines using a user defined subroutine. Comparisons on the keys are done lexicographically.

While it sorts these keys lexicographically, there is room to munge the keyspace to do as you need. If you want your own sort routine, you can roll your own easily enough.