The XML::Filter::Sort module allows sorting arbitrarily large amount of data which is in XML format. You could use it like this:

1. convert your data to XML (eg: <rec id="999999" Name="John Doe" ... /> ...)
2. parse the XML file with a SAX parser that passes events to ...
3. XML::Filter::Sort which sorts the events and passes them to ...
4. XML::SAX::Writer which outputs an XML file
5. convert the XML back to you original format

However, since XML::Filter::Sort is a SAX filter (rather than an XML filter), it's not actually necessary to use XML data at any stage of the game. Instead you could do it like this:

1. write a simple SAX generator class (inherit from SAX::Base) which reads the text file and generates SAX events to ...
2. XML::Filter::Sort which sorts the events and passes them to ...
3. a simple SAX handler class which accepts events and writes out plain text in the original format

Although you didn't list maintainability as a key requirement, this type of arrangement would separate your code into logical units which each implement a well defined subset of the whole operation.