Unsorting(randomizing) a sequence

[Tim Peters]

[Jeremy Hylton]
> ...
> 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),

Indeed, I'm *thrilled* to be associated with this worthless method, Jeremy!
I must have it inscribed on my tombstone.

> depends an awful lot on the Python quicksort implementation (another
> good reason to call it the Tim Peter's method <wink>).

Since Python no longer uses a quicksort, that's even more appropriate
<wink>.

[attempting to explain shufflesort's bad behavior]
> ...
> I think this follows from the quicksort approach.
> ...

It certainly depends on the details of the sort implementation.  For the
size of inputs you've been looking at, Python actually uses a pure binary
insertion sort after finding the longest already-sorted prefix, and the only
comparison outcome it looks at is the two-way "less than, or not?".  Your
choice function gives equal weights to -1, 0 and 1, the latter two of which
the sort takes as meaning "no".

For the two-element case, it will leave the input alone 75% of the time.
Now you'll have no problem completing an exact analysis for the general case
<wink>>

almost-done-with-the-N=1-case-myself-ly y'rs  - tim