You should try use diagnostics; when things get tough, and use warnings; unless you really know you wont need it (you seldom can know that), but the hints use warnings and diagnostics would give here isn't trivial to understand.
You are just overdoing your sort criteria:

use strict;
use warnings;

my @AoH = (
       {a => 1,  b  => 2,  c  => 3},
       {a => 1,  b  => 2},
       {a => 1,  b  => 2,  c  => 3,  d  => 4},
       {a => 1}
);

my @AoH_sorted = sort { (keys(%{$b})) <=> (keys(%{$a})) } @AoH;

foreach my $i (0 .. $#AoH_sorted) {
  print "$i\t";
#  if (exists  $AoH_sorted[$i]) { # no need to check if exist when usi
+ng foreach
    my %hash = %{$AoH_sorted[$i]};
    foreach my $key (keys %hash) {
      print "$key\t";
    }
#  }
  print "\n";
}
[download]

gives:

0       c       a       b       d
1       c       a       b
2       a       b
3       a
[download]