ikegami's solution is a good one then - cache the sorted keys. You can even forgo the foreach loop using hash Slices:

my @sorted_keys = sort { $a <=> $b } keys(%foo);
print join("\n",@hash{@sorted_keys})
[download]