Additional information, such as a normal dense array containing the sorted hash keys, are needed in order to allow iteration though.

Of course you can obtain that on the fly trivially with foreach( sort { $a <=> $b } keys %sparse ). It's really more of an efficiency question whether you want to keep that seperately or do it each time (and either way could be done transparently with a tied array).