alakaboo mentions Date::Manip which is an excellent module but is very much a heavyweight module (in fact, the POD for Date::Manip even recommends not to use it if you're looking for simple date transformations of the form you're looking for). Try using Time::ParseDate which is much more lightweight and does exactly what you're looking for too much else. Combine it with a Schwartzian transform (see merlyn's post above) like so:

use Time::Parsedate;
...

foreach my $day (
  map { $_->[0] } sort { $a->[1] <=> $b->[1] }
    map { [ $_, parsedate( $_ ) ] } @dates
) {
  ...
}
[download]

And that will be all she wrote. parsedate() from Time::Parsedate is pretty speedy and comparing the dates using a simple numeric compare is probably going to be faster than using Date_Cmp() (parsedate() returns numeric timestamps).