No, this is quite efficient. Hash accesses are very fast ... You really should test whether you get any speedup through this

Here is some benchmark code that explores this.

use strict;
use warnings;

use Benchmark q{cmpthese};

my %hash =
   map { $_ => { Size => int rand 10000 } }
   q{aaa} .. q{dzz};

my $rcJethro = sub
   {
       my @unsort = map qq{$hash{ $_ }->{ Size }:$_}, keys %hash;

       my @sort = do
          {
              no warnings q{numeric};
              sort { $a <=> $b } @unsort;
          };

       foreach ( @sort )
       { 
           s{[^:]*:}{};
       }

   };

my $rcSimple = sub
   {
       my @sortedKeys =
          sort { $hash{ $a }->{ Size } <=> $hash{ $b }->{ Size } }
          keys %hash;
   };

my $rcClassicST = sub
   {
       my @sortedKeys =
          map  { $_->[ 0 ] }
          sort { $a->[ 1 ] <=> $b->[ 1 ] }
          map  { [ $_, $hash{ $_ }->{ Size } ] }
          keys %hash;
   };

my $rcClassicGRT = sub
   {
       my @sortedKeys =
          map { substr $_, 4 }
          sort
          map { pack q{NA*}, $hash{ $_ }->{ Size }, $_ }
          keys %hash;
   };


cmpthese(
   -5,
   {
       ClassicGRT => $rcClassicGRT,
       ClassicST  => $rcClassicST,
       Jethro     => $rcJethro,
       Simple     => $rcSimple
   }
   );
[download]

The output.

             Rate     Simple  ClassicST     Jethro ClassicGRT
Simple     11.3/s         --       -13%       -46%       -55%
ClassicST  13.0/s        16%         --       -37%       -48%
Jethro     20.8/s        84%        59%         --       -17%
ClassicGRT 25.0/s       122%        92%        20%         --
[download]

Your sorting code is a bit odd in that it appears to be a halfway house between a ST and a GRT. It has some issues with "numeric" warnings and a reliance on Perl doing the right thing (which is does at the moment but perhaps that might change) when doing a numerical sort on non-numerical strings that happen to have leading digits. It is pretty quick though, only beaten by the GRT. I have altered your code a bit by using simple interpolation in the map instead of concatenation and by localising and better targetting the no warnings instruction.

The usual caveats apply regarding my benchmarks. I've cocked them up before and I'm sure I will again.

Cheers,

JohnGG

Update: Corrected typo, s/you/your/