I've found that sorting large files (i.e. millions of lines of text, 100s of MB in size) in practice is very hard to do efficiently in Perl. It's possible to get solutions, e.g. via CPAN modules, that work for certains types of data or certain data set sizes. It is also easy to introduce memory/CPU/disk hogging behavior as well, and then spending lots of time tracking them down.

If you don't need portability to platforms that don't support using 'sort', I'd suggest following graff's advice about transforming the data and then using Unix's sort command. This kind of implementation is straightforward, quick, and generally robust.