It's certainly true that the sort algorithm used would affect the fairness. For bubblesort, it would seem that the random probability of a swap would need to be adjusted. Possibly (N-1)/N would be right, or possibly it would have to change with each pass.

But Perl uses mergesort, which doesn't find an element's place and then never look at it again. Or you can select quicksort, which actually does take an element and stick it somewhere in the middle, after which it never moves again.