How about mix of map and sort:

my $idx;
my @sorted = map { $arr1[$_->[0]] }
             sort { $a->[1] <=> $b->[1] }
             map { [$idx++, $_] }
             @arr2;
[download]