In addition to the problems noted by others, it seems like sorting first and renaming afterwards would be a waste of effort; "%Y%m%d" will automatically sort correctly in most situations, which is part of the point of doing it that way. Also, if you start renaming your files and run into a duplicate date part-way through, you'll end up with a scattered list of filenames. It would be better to validate before you ever start renaming. You might want to consider something like this:

#!/usr/bin/perl -w
use strict;
use POSIX;

my %seen;
while (<*.gz>){
    my $date = strftime "%Y%m%d", localtime((lstat($_))[9]);
    my $was = $_;
    s/\d+/$date/;
    die "File '$_' already exists!\n" if -f $_;
    die "We already have a file with that date ($date).\n" if $seen{$_
+};
    $seen{$_} = $was;
}

for my $fn (sort keys %seen){
    rename $seen{$fn}, $fn;
    print "$fn\n";
}
[download]