I've turned on warnings because I didn't get what's wrong with your code (which looks correct at first glance) and suddenly...
-bash$ xsel -o | perl -w
Name "main::d" used only once: possible typo at - line 9.
Use of uninitialized value $d in numeric comparison (<=>) at - line 9.
Use of uninitialized value $d in numeric comparison (<=>) at - line 9.
20130601 20130501 20130401
It looks like $d is never initialized in the first place, and evaluates to 0 in a numeric comparison. So to make life a bit easier, I would suggest always turning on strict and warnings:
#!/usr/bin/perl
use strict;
use warnings; # or just #!/usr/bin/perl -w on first line
my @dates = ('20130401', '20130501', '20130601');
my @ordered = sort { &compare } @dates;
print "@ordered\n";
sub compare {
$a =~ /(\d{4})(\d{2})(\d{2})/;
my $c = $3 . $2 . $1;
$b =~ /(\d{4})(\d{2})(\d{2})/;
my $d = $3 . $2 . $1;
$c <=> $d;
}
And now typing $c instead of $d makes program crash on the compilation stage, instead of silently corrupting data. Also note the "my" keyword - in strict mode you have to declare your variables, instead of just using them (and probably destroying previous data). ($a and $b are special vars that require no "my" though).