Sorry, maybe I just don't get it, but why is your first example a stable sort?

my @unsorted = 
  ([1,1], [2,1], [1,2], [2,2], [2,3], [1,3], [2,4], [1,4]);

print join( ' ', 
  map { $_->[0].$_->[1] } 
    sort { $a->[0] <=> $b->[0] } @unsorted) . "\n";

my @sortedindices = sort 
  { $unsorted[$a]->[0] <=> $unsorted[$b]->[0] } 
  0..$#unsorted;

print join ( ' ', map { $_->[0].$_->[1] } 
  @unsorted[@sortedindices]);
__END__
11 12 13 14 23 21 24 22
11 12 13 14 23 21 24 22
[download]

Both sorts are not stable.

daniel.

update: got it now ;-) replace compare-function by

$unsorted[$a]->[0] <=> $unsorted[$b]->[0] || $a <=> $b
[download]