I hope you are aware that hashes are not sorted, so as Perl data structures the following two are exactly equivalent:

 {
    3 => 15,
    4 => 8,
    5 => 9,
 }
# and
 { 
    4 => 8, 
    5 => 9, 
    3 => 15, 
 }
[download]

So you can either sort and print, or sort and store in a different data structure - sorting and trying to store it in a another array of hashes doesn't make sense.