in reply to
Re^4: In-place sort with order assignment
in thread In-place sort with order assignment
Not that this seems to help you very much but sort was my first instinct too. My rather dated Debian Squeeze box is an AMD 3800+ (64 bit dual core) with 2 gigs RAM and one 5 year old IDE drive can almost do it.
$ perl 860849.pl
Took 131.000000 seconds for 10000000 items (0.00001 per second)
I think I could reach that 108 by putting the sorted file on a separate spindle with a thinner filesystem layer (e.g. no ext3 and LVM2).
I'm really pointing this out because it's quite attainable with a reasonably recent hard drive. Maybe even just SATA/PATA would do the trick. SSD surely would.