perhaps this suits your needs?

use Data::Dumper;
my @r = ( 
  [ 5, 3, 5, 5 ],
  [ 1, 1, 2, 1 ],
  [ 2, 1, 2, 3 ],
  [ 5, 5, 1, 5 ],
  [ 1, 5, 1, 1 ],
  [ 2, 3, 5, 3 ]
);
@x =  sort { $a->[2] <=> $b->[0] || $a->[3] <=> $b->[1] || -1 } @r;
print Dumper(\@x);
__OUTPUT__
[ 1, 5, 1, 1 ]
[ 1, 1, 2, 1 ]
[ 2, 1, 2, 3 ]
[ 2, 3, 5, 3 ]
[ 5, 3, 5, 5 ]
[ 5, 5, 1, 5 ]
[download]

Update: As Jaap found out, it did not work always, so here is my next try:

for my $i (0..$#r) {
  my $p = $i + 1;
  for my $j ($p .. $#r) {
    next unless $r[$i]->[2] == $r[$j]->[0] 
             && $r[$i]->[3] == $r[$j]->[1];
    @r[$p, $j] = @r[$j, $p];
    last;
  }
}
[download]