merlyn had probably the most simple solution. I, however, like the creative solution. AoH or Hash based solutions are obvious. How's this for a unique method:

my @a = qw(fred bob john peter);
my @b =   ( 2, 1, 4, 3 );

my @a_sorted = @b_sorted = ();

push( @{ ($|-- ? \@b_sorted : \@a_sorted ) }, $_ ) for
    map  {           @$_           }
    sort {   $a->[1] <=> $b->[1]   }
    map  { [ $a[$_],     $b[$_]  ] } (0 .. $#b);

print " $a_sorted[$_]  => $b_sorted[$_] \n" for ( 0 .. $#b_sorted );
[download]

The one thing that I don't like about this is that it does not sort in place. It requires the creation of two new sorted arrays. :-(