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 ]
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.
Makeshifts last the longest.