It might be worth investigating a solution that inserts the data in a DBD::SQLite database then just sorts using a SELECT. I've seen this applied with very good results to munging huge logfiles - although not anywhere near the size you mention, so I'm not sure how well it will work for you. In any case, I'd give it a shot - if it works, it'll be hardly more than two dozen lines of code (mostly DBI red tape) and pretty efficient too.

Makeshifts last the longest.