For “millions of keys,” consider tieing it to, say, a Berkeley DB file.   For such a file, the each() function will return the values in ascending order by key, without the need for a separate sort.

Include a field, sort_position, initially zero.   Then, after the structure is loaded, walk the keys and assign the values sequentially.

Since you are, probably of-necessity, creating a persistent representation of the hash (an ISAM-file), try to structure your entire process to take advantage of that persistence.   The first run, which loads the file for the first time, would be the most expensive.

Also consider ... doing it the COBOL way.   Instead of relying upon random-access data structures of any kind, use an external-sort to sort both the master file and any update-files by the same key.   Then, process the two streams sequentially, in so-called “unit record” fashion.   You just might be astounded at how much faster it works ...