The hashkeys are not stored sorted, no. But, in doing a sort (and I could be wrong), Perl doesn't necessarily pull all the data into memory. If it does, then I would certainly accept help in getting Perl to do the sort in the way you're describing.
My criteria for good software:
Does it work?
Can someone else come in, make a change, and be reasonably certain no bugs were introduced?