Since only unique elements are addressable through your lookup table (@sorted_indexes), why are the duplicates kept?

When you have multiple parallel arrays, it's usually easier to just sort the indexes.

my @names = qw( Alice  Bob      Eve );
my @roles = qw( sender receiver evesdropper );

my @lookup = sort { $names[$b] cmp $names[$a] } 0..$#names;

for my $i (@lookup) {
   print("$names[$i]: $roles[$i]\n");
}
[download]

Notice how the results are sorted (by name in descending order) while the relation between name and role isn't broken?