Using split, a hash for month sort order look-ups and a ST seems simplest.

$ perl -Mstrict -Mwarnings -E '
my %mthSO = do {
   my $order;
   map { $_, ++ $order } qw{
      Jan Feb Mar Apr
      May Jun Jul Aug
      Sep Oct Nov Dec
      };
   };

say for
   map  { $_->[ 0 ] }
   sort {
          $a->[ 2 ] <=> $b->[ 2 ]
          ||
          $mthSO{ $a->[ 1 ] } <=> $mthSO{ $b->[ 1 ] }
        }
   map  { [ $_, split m{ (?<= [a-z] ) (?= \d ) }x ] }
   qw{ May14 Dec13 Mar14 Oct12 Apr14 };'
Oct12
Dec13
Mar14
Apr14
May14
$
[download]

I hope this is helpful.

Update: Corrected lame-brain wrong comparator for month, thanks AnomalousMonk ++