"James Stark" <james_stark03 at hotmail.com> wrote:

	quicksort: begin to: end
	
Which class is this from?

	    pivot := self basicAt: middle.
	
I am always suspicious of code that uses #basicAt:.  It should be rare.
	
	I can confrim that this algorithm does not work - its crap.

I take it that this means you have a test case which it gets wrong?

	Actually its
	meant to assign the pivot value to the left to start off with.
	
You need to be aware that there are many variants of quicksort.  Quite
a few of them don't do that.

	If any of you guys have developed any other algortihms it would be 
	interesting to do a trace.  Like a binary tree sort (is that more 
	efficient?) I dont know... just traced that one - made no sense.
	
Sense shmense.  Did it give the right answer?

If you poke around in Squeak 3.0, you will find
 - a quicksort in SortedCollection>>sort:to:
 - a Heap Sort example in SortedCollection class>>heapSortExample
 - a merge sort in ArrayedCollection>>sort:

Merge sort is a good general-purpose sorting method which, if written
carefully, can easily out-perform quick-sort.  (Yes yes, I know the papers
that are supposed to prove quicksort fast.  They assume that comparisons
are dirt cheap; in one paper 1/4 of the cost of a memory reference.  In a
system like Squeak where comparison blocks are involved, comparisons are
not cheap.)