From perldoc -f sort:

The comparison function is required to behave. If it returns inconsistent results (sometimes saying $x[1] is less than $x[2] and sometimes saying the opposite, for example) the results are not well-defined.

And "not well-defined" should never be interpreted as "uniformly random." Uniformity is an extremely specific statistical property that in general does not just happen naturally.

Something closer to what you have in mind is probably the following Schwartzian Transform:

  map { $_->[0] }
  sort { $a->[1] <=> $b->[1] }
  map { [ $_, rand 1 ] } @array
[download]

This is a fair shuffle. Each element is equally likely to have the smallest corresponding random value (and therefore be first). Then each remaining element is equally likely to be the smallest among the remaining elements, and so on. This is the definition of a uniformly chosen permutation.

The key difference from your example is that we assign the random values first, then sort. So here, the comparisons are self-consistent.

Update: expanding more on the definition of a "well-behaved" comparison function: The text of the POD is slightly misleading. While sorting a single list, the sorting algorithm never needs to compare the same pair of elements twice. What "well-behaved" really means is that all the comparisons made indeed correspond to a linear ordering of the elements. For instance, when sorting (A,B,C), the random coin-flips might work out so that the comparisons return A<B, B<C, and C<A. This is not a linear order (not even a partial order), and this is exactly when the sorting algorithm's behavior is undefined.

To be clear about the distinction between the two examples: In my ST example, all the randomness is fixed before the sorting algorithm is called. You are just sorting a list of random numbers numerically, and the numbers don't change in the middle of the sort, so there is no problem at all.