He's right, the "pivot" (in quicksort terms) is always selected as the
first for this degenerate case, this line is at fault:

[l _ l - 1.  k <= l and: [self should: dij precede: (array at: l)]]
				   whileTrue.  "i.e. while dl succeeds dij"

Since "self should: x precede: x" is always true for sortBlock = [:x:y |
x <= y]. So l zips right to the beginning, and that's where the
recursion becomes very unbalanced.

I personally don't feel very much compelled to "fix" this by changing
the sort. One might argue that giving a sort block like <= and many
equal values, if it isn't itself a bug, certainly deserves some
punishment ;-)

Ned Konz <ned at bike-nomad.com> wrote:
> On Wednesday 01 May 2002 09:59 am, David A. Smith wrote:
> > Well, actually...
> >
> > The default for #asSortedCollection is <=.
> > If instead, one were to replace this with:
> >
> > [((1 to: 10000) collect: [:x |3]) asSorterdCollection:[ :a :b | 
> > a<b ] timeToRun ==> 183
> >
> > compared with:
> >
> > [((1 to: 10000) collect: [:x |3]) asSorterdCollection:[ :a :b |
> > a<=b]] timeToRun ==> 29150
> >
> > Obviously, the comparison is always true, hence something always
> > happens (probably a swap).
> >
> > Hence, not a bug - though I think sorting on <= is inefficient.
> 
> It is, but I think there is a bug.
> 
> The main problem seems to be that defaultSort:to: recurses way too 
> much. I'd expect its recursion depth to max out at log2(size) (I 
> think), but it's going down to about (size).
> 
> I ran it on 100 items, and it got to a recursion depth of 98 (!). 
> Twice.
> 
> defaultSort: 1 to: 1000
>    calls defaultSort: 1 to: 0
>   and defaultSort: 2 to: 1000
> 
> which doesn't seem right. For one thing, sorting 1 to: 0 is a waste of 
> time.
> 
> -- 
> Ned Konz
> http://bike-nomad.com
> GPG key ID: BEEA7EFE