If you're going to go to the trouble of two s/// operations, you might as well go all the way to a GRT/decorate-sort-undecorate solution; then you can at least claim to be getting the maximum possible performance from the Perl sort built-in.
c:\@Work\Perl\monks>perl -wMstrict -le
"my %data = qw(
Dec02 2 Jan02 3 May05 4 Dec14 8 Dec01 5
Jan14 7 Apr05 6 Feb14 9 May15 10
);
;;
use constant Y_WID => 2;
use constant M_WID => 3;
my %mon_n = qw(
Jan 1 Feb 2 Mar 3 Apr 4 May 5 Jun 6
Jul 7 Aug 8 Sep 9 Oct 10 Nov 11 Dec 12
);
;;
my @sorted_dates =
map unpack(qq{x${\Y_WID} x${\M_WID} a*}, $_),
sort
map sprintf('%*s%*s%s', Y_WID, $_->[1], M_WID, $mon_n{$_->[0]}, $_-
+>[2]),
map [ m{ \A ([[:alpha:]]{${\M_WID}}) (\d{${\Y_WID}}) \z }xms, $_ ],
keys %data
;
;;
print qq{Key - $_ and b value - $data{$_}} for @sorted_dates;
"
Key - Dec01 and b value - 5
Key - Jan02 and b value - 3
Key - Dec02 and b value - 2
Key - Apr05 and b value - 6
Key - May05 and b value - 4
Key - Jan14 and b value - 7
Key - Feb14 and b value - 9
Key - Dec14 and b value - 8
Key - May15 and b value - 10
Update: See A Fresh Look at Efficient Perl Sorting by Guttman and Rosler (the G and R of GRT). Also: It seems to me now that all the regex sub-string extraction and sprintf-ing would have been much neater, clearer and more maintainable if encapsulated into a separate function. Oh, well...