there is no way to associate the keys with the resultant sorted values--which was a requirement for the OP.

I didn't see that. To be honest I thought his requirements were somewhat poorly specified. In any case, you can just swap value-ordering for key-ordering by saying

( keys %hash )[ order_of_sorted keys %hash ]
[download]

You then have to fetch the values in an extra step by looking up the keys. That's additional work, but you have the keys available in $outer and $inner for later perusal.

This just goes to show my point: separating the problems well improves maintainability.