While it may seem goofy, I feel your best bet is to go through a database, and let it do all of the heavy lifting, or sorting, of data. You can run out of memory a lot faster than a database will run out of disk space.

You may have to write scripts to load the data, or you may be able to get the database to do that .. I've used bcp on Ingres, and LOAD INFILE (or something like that) in MySQL to do that. Again, my preference would be to go with the database provided tool, but a quick script will probably do the job too.

And I highly recommend a few test runs with just 100 or so records to make you're doing it right before unleashing millions of records on the database.