Hi Georg.

> >>  addAll: aCollection
> >>          "Optimize for large additions."
> >>
> >>          aCollection size > (self size // 3) ifTrue: [
> >>                  aCollection do: [ :each | super addLast: each ].
> >>                  self reSort ]
> >>           ifFalse: [ aCollection do: [ :each | self add: each ]].
> >>          ^aCollection! !
>
> Sorry, I do not understand this one. Can you elaborate ?

The message addAll: works by adding stuff to the receiver. Hence,

x addAll: aCollection

gets you x with all its elements plus the elements of aCollection, all of
those in x. aCollection is not modified by this process. Now, with the method
above, you may get an equivalent answer but the receiver may be left untouched
by addAll:. This would happen when aCollection size <= (self size // 3). In
that case, aCollection would have its elements and those of x, so the answer
of this message would be equivalent. But aCollection is modified instead of x.
So, you could have this happen:

x _ (1 to: 10) asSortedCollection.
y _ (11 to: 12) asSortedCollection.
x addAll: y.
x size <alt-p> 10

How come it's 10 when I added stuff to it? And surprisingly,

y size <alt-p> 12

?!??!...

What I meant by merge sort is that when collections are large, the cost of
resorting is huge. So, when addAll: is sent with a big collection to another
big collection, you could do merge sort and create a third temp one whose
contents would replace the receiver's when the process is finished. Alas, you
can only do this if the sort blocks are both nil or are compatible.

I do not think that the sort blocks can be determined to be compatible... it
would take too much (even if they sent the same messages, you would also have
to verify that they were supposed to send the same messages to the same kind
of objects). That leaves the case when the sort blocks are both nil, in which
you can safely do merge sort.

Andres.