See fast, flexible, stable sort. I've translated your code using that idea.

sub parasort
{
    my $sort = shift;
    my $independent_array = shift;
    my @dependent_arrays = @_;

    my @sort_ix = 
        map unpack( 'N', substr( $_, -4 ) ),
        sort
        map &$sort( $independent_array->[ $_ ] ) . pack( 'N', $_ ),
        0 .. $#$independent_array;

    return map [ @{ $_ }[ @sort_ix ] ],
               $independent_array,
               @dependent_arrays ;
}
[download]