Unsorting(randomizing) a sequence

[Tim Peters]

> | def randomize(a, b):
> |     return random.choice([-1, 0, 1])
> |
> | l = range(2, 20)
> | l.sort(randomize)

[Dan Schmidt]
> I'm not sure how robust this is.  I've seen at least one implementation
> of qsort crash when given an inconsistent comparison function (e.g.,
> one that doesn't obey transitivity).

Python implements its own sort function (in 1.5.2 it's not quicksort, btw,
but a hybrid of common special cases, binary insertion and samplesort).  A
very long time ago it used the platform qsort, but that blew up on some
systems; iirc, usually due to qsort being implemented non-reentrantly.  The
current sort is robust against all that kind of stuff, including insane
comparison functions; it always returns *some* permutation of its input.

> And how is sort() supposed to know when it's done?

Surprisingly simple <wink>:

			/* Find another slice to work on. */
			if (--top < 0)
				break;   /* no more -- done! */

insane-comparators-simply-yield-insane-meanings-for-"sorted"-ly
    y'rs  - tim