Okay, live-ish results:

Summary:

• 5M small records sorted in 1.0 minutes on my system
• RAM usage appeared to peak at about 522 MB.

Details:

• 2.78GB sitting at the command prompt
• 2.78GB running a doNothing.pl script (negligible overhead for Perl)
• gendat.pl ran 2.5 minutes
  • Generated 5M lines
  • Lengths of lines were randomized from 1-100
  • Key pairs were randomly generated as key1-key43 each.
• 2.76GB sitting at the command prompt
• TwoKeySort.pl ran 1.0 minutes
• 3.27GB peak RAM during TwoKeySort.pl
  • (0.51GB = 0.51 * 1024 = 522.25 MB.)
  • A little larger than anticipated
  • Either my guess at a Perl's hash overhead needs to be tripled, or;
  • I missed other intermediate storage requirements
• 2.77GB after perl script ended and about 45 seconds for memory to be reclaimed

  So it takes a little over 500MB on my machine. This is a 64-bit system so if my version of Perl does 64-bit integers this should be fairly indicative. It might need to double otherwise; leaving you with, potentially, a 1GB commit using this technique.

  If 100MB was just a wag, then I would hope you wouldn't balk at using a half GB of RAM to sort a 20GB file using no intermediate disk space.

  Alternatively, you could write the key/key/offset/length values to a file which would be closer to 120MB; sort it, then read it in to guide the binary random I/O process. Just replace 522MB of RAM with a 120MB file, and use an external sort routine.

  The time estimate is not indicative since I had no 5MB lines to read, and I/O is still probably the slowest function on the system (though I haven't really kept up on the industry tech specs, going on assumption here).

  So there you have it. I didn't cache any of the data lines (that was kind of the point of this approach) so this should be a fair representation of space consumed for 5M lines, since the size of the lines don't matter.

  If you really have to keep it to 100MB, the 43 x 43 = 1849 passes through the source file might be your best bet. It will be slow, but effective.

  One other possibility, if you really want to over-engineer this thing, is you could segment the work. One approach for this has already been suggested, but given the low memory usage for the hash and array data, you could consider writing just the hash out to intermediate files to be gang-sorted using some kind of segmented iterative approach.

  That would be fun, but almost certainly not worth the effort.

  Have fun!

  Comment on Re: sorting type question- space problems