Reading this made me think of Data Structures classes in university. In C, I would read the keys into a tree structure rather than a hash, then assign sequence numbers by doing an in-order traversal. But the extra pointers involved probably waste nearly as much space as the duplicate list, and rebalancing the tree burns a lot of CPU.

The external sort is probably the best Perl solution.