Unsorting(randomizing) a sequence

[Jeremy Hylton]

Thanks for the analysis!  I admit that metrics I used when I judged the 
randomizer I posted to be of high quality were: (1) ability to fit in
a single line and (2) obscurity.  I didn't mean to imply that the
method was good according to any other metric.

>The "hylton" method favors even permutations over odd ones, tends to
>produce increasing sequences, and distributes the variance unequally,
>apparently peaking near the beginning (1/e of the way through?).  I
>haven't quite fully analyzed the reasons for this yet...

The "shufflesort" or "Tim Peters" method, which I would offer as
preferred names (because I don't particularly want my name associated
with it and Tim's name is as good as anyone's), depends an awful lot
on the Python quicksort implementation (another good reason to call it 
the Tim Peter's method <wink>).  

I expect that the reason its tends to produce increasing sequences is
that you started with a sorted sequence; if you reverse the sequence,
it will probably tend towards decreasing sequences.  I think this
follows from the quicksort approach.  Quicksort is going to divide
each list into two sublists where the each element of the first
sublist is less than or equal to each element of the second sublist.

Since the comparison function is random, the sort is just going to
exchange a random number of elements around the pivot point.  Then
quicksort is going to be applied to each sublist, so no element from
the second sublist is ever going to be moved to the other side of the
original pivot point.  The end result is that the shufflesort method
will often leave elements close to where they were originally.

Jeremy