Points 1 - 3: Perhaps an Orcish Maneuver might help? Like the example below that caches results as it goes. The concept is similar.

my %m = ();
@sorted = sort {
  ($m{$a} ||= -M $a) <=> ($m{$b} ||= -M $b)
} @files;
[download]

Points 4 & 5: I thought that's called the element ranking?

my @rank[sort {$x[$a] cmp $x[$b] } 0..$#x] = 0..$#x;
[download]

I would imagine the solution might be a combination of the two algorithms, plus some tweaking.