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@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
squeak-dev@lists.squeakfoundation.org