It's a long way around to do it, but maybe you have your reasons.

#! perl -slw
use strict;
use Data::Dumper;

my @array1 = (
    "john:::10",
    "bill:::9",
    "mary:::35",
    "willy:::21",
);

## Build @array2 from the numbers in @array1
my @array2 = map{ m[(\d+)$] and $1 } @array1;

## Reorder @array1 by assigning a slice across it 
## with the indexes sorted according to the numeric values in @array2
@array1 = @array1[ sort { $array2[ $a ] <=> $array2[ $b ] } 0 .. $#arr
+ay2 ];

print Dumper \@array1;

__END__
P:\test>385906
$VAR1 = [
          'bill:::9',
          'john:::10',
          'willy:::21',
          'mary:::35'
        ];
[download]