The exact proof is simple. There is a maximum number of
comparisons K which may be needed to sort the list of length
N. Each comparison gives a random binary decision.
Therefore we have 2**K equally likely outcomes, each of
which winds up with some sort order. And we have N!
possible sort orders. Now can the sort orders possibly
all come out even? The answer is no for N larger than 2
because if N is at least 3 then N! is divisible by 3, and
therefore 1/N! has an infinite (repeating) decimal expansion
while 1/2**K has a decimal expansion that terminates,
therefore the actual probabilities of the buckets all have
terminating expansions.
Which sort orders are favoured depends on the details of
the sort algorithm.
Now if you want the idea of using a sort to scramble
elements, you can do it with a Schwartzian sort. Like this:
my @shuffled = map {$_->[1]}
sort {$a->[0] <=> $b->[0]}
map {[rand(), $_]} @orig;
Or use Fischer-Yates as often discussed.
BTW I am using infinite decimals vs non-infinite as a
shortcut here to avoid talking about divisibility. This
works because we talk about base 10, and 2 divides 10. But
this is but one of a family of math arguments based on
divisibility. For an example of another fun one, it is not
hard to show that the Gregorian calendar has a number of
days divisible by 7 but not 49. From that you can show,
for instance, that the thirteenth of the month does not fall
exactly evenly between the days of the week. It takes
considerably more effort to figure out that the 13'th falls
on Friday more often than straight chance would lead you to
expect. :-) |