I was trying to figure out how to explain why this was
going to give a perfect sort, and I realized that in fact
this trick simply cannot give a perfect sort for an
array of size larger than 2 when fed an algorithm with
bounded performance!
This is cute.
As the above makes clear, you are basically making random
coin flips until it spits out an answer. If the array has
n entries, there is some maximum number of flips, say k,
that you could be asked for.
Turning it around on its head I could just ask you up front
to make k coin flips, then feed that into the algorithm,
and get an answer. Now there are 2^k possible sequences
that you could give me, and they are all equally likely.
So if you write in base 2, the probability of any particular
permutation is 2^(-k) times the number of sequences that
gave that permutation.
What that is I don't care. What I do care about is that
when written out in base 2 that probability is a decimal
that terminates after at most k places. But for each
permutation the probability we really want is 1/n!, and if
n is bigger than 2 then n! is divisible by 3 which is *not*
a power of two so 1/n! has to be (base 2) an infinite
repeating decimal!
In other words I may not, without calculating it, have any
idea how your anwer will be biased, but in fact it is!
ObTrivia: A somewhat similar counting argument manages to
show that the 400 year Gregorian calendar repeats days of
the week, but cannot divide a particular day of the month
between them. However it takes explicit calculation to
show that the 13'th falls on Friday more than 1 day in 7. |