Or, I just faced that very problem here (Ordering objects using external index). The one you derived from original question in this thread. I think that my method is a little faster than yours but not that fast that I'd expect anyway.

#!/usr/bin/perl
use strict;
use warnings;

my @arr1 = qw(john:::10 bill:::9 mary:::35 willy:::21);
my @arr2 = qw(9 35 10 21);

my %hash = map { $_ =~ /:::(\d+)$/; ($1 => \$_); } @arr1;
print for map { $$_ } @hash{@arr2};
[download]

No sorts. References are optional, of course.