If you translated your data to XML, you could sort it with XML::Filter::Sort (which I uploaded to CPAN a few days ago). One feature of this module is that you can specify the amount of memory (not including interpreter overheads) that the sort can use. Any overflow will be handled by using temporary sort/merge files.

I'm not going to pretend it would be fast though - probably several orders of magnitude slower than what you're doing now.