If execution time is important and the number of items being sorted is large enough or the calculation per item is expensive enough it is worth caching each calculated sort value. The classic pattern for that is:

my @sortedKeys = 
    map {$_->[1]}
    sort {$a->[0] cmp $b->[0]}
    map {[function($_), $_]} keys %hash;
[download]

which generates then sorts a list of sort_value, key_value pairs and returns the sorted keys.