Jerzy Karczmarczuk <karczma at info.unicaen.fr> wrote:
	Making random permutations is costly, and *usually* useless.
	Several real implementations use just the median discrimination:
	choose 3 items, e. g., first, last, and something in the middle,
	and use the median one as the pivot.

Yes, and it Isn't Good Enough.  There's a reason why the Bentley &
McIlroy code uses median-of-medians whenever it can.

Quicksort is O(N**2).  Period.  It's like hammering a dent out of your
car.  Hammer hammer on the dent, and lo! it pops out somewhere else.
The dodges and devices people have come up with for reducing the dent
(but not eliminating it) basically boil down to "make it less like
quicksort and more like something else".  My favourite appeared in the
Bell System Technical Journal.  In a paper on improving the System V
sort(1) command, the author *almost* reinvented merge sort, and if only
he had thought of using linked lists, he'd have got there.  (According
to that paper, the System V sort(1) command after he'd finished with it
would read as much as it could into memory, chop that up into 32 pieces,
sort each piece with qsort, and then merge the pieces.)

There are easy-to-construct sequences which defeat median-of-three.

The really sad thing is that when Hoare invented quicksort, he *knew*
that merge sort was more efficient.  It's there in his paper.  It's
just that he had to sort lots of numbers on a machine with only
256 words (no, I did not omit a "k" there) of main memory (and a backing
store of 2**16 words, transferred in 64 word blocks), so memory really
was the limiting resource.  These days, if you're not sorting on a
digital wristwatch, there is seldom any reason to use quicksort.

Since Squeak *already* includes quite adequate sorting code,
there is no need for anyone to write yet another not-as-quick-as-you-might-
expect-sort for it.