Let's look at what you're doing here (slightly reformatted):

%foo = (
  11 =>{ 4 => 'Four' },  
  33 =>{ 1 => 'One'  },
  2  =>{ 2 => 'Two'  }
);

my $ref_HoH = \%foo;

for my $k ( sort 
               { %{ $ref_HoH{$a} } <=> %{ $ref_HoH{$b} } }
               keys %$ref_HoH ) {
...
}
[download]

Your sort routine is sorting on the values of each hash entry. That means you're sorting by memory address, since the value of each entry is an anonymous hash, so you are looking at the addresses of each anonymous hash.

All you really need is to simplify the sort (Hey, make it simple, what good news!)

use strict;
use warnings;

my %foo = (
   11 => { '4'=>'Four', },
   33 => { '1'=>'One', },
   2 => { '2' => 'Two', },
);


my $ref_HoH = \%foo;

for my $k ( sort { $a <=> $b } keys %$ref_HoH ) {
   print "$k\n";
}
[download]

hf@flux[30] perl /tmp/testit
2
11
33
[download]

I'll leave the rest as an exercise for the OP.

~Jeff