Why SortedCollection sort: and sortBlock: do not uses the same method to sort?

[MarcusDenker]

from: https://pharo.fogbugz.com/f/cases/17925/Why-SortedCollection-sort-and-sortBlock-do-not-uses-the-same-method-to-sort

sortBlock: uses SortedCollection>>sort:to: algorithm (kind of merge sort) and sort: the mergeSort on Array.

[kasperosterbye]

It seems even more odd than what Marcus describes. The #sort: method is implemented in these collection classes:

SequenceableCollection -> uses its own implementation of mergesort
OrderedCollection -> delegates to the mergesort array inherits from Sequencable collection
SortedCollection -> deletates to the algorithm in SequenceableCollection
LinkedList -> uses the same as the above
Heap -> One whould think that heap used heap sort, but it seems to use a COPY of the mergesort found in SequenceableCollection.

Finally, as Marcus noticed, the #sortBlock: of SortedCollection uses a #sort:to: mergesort implemented in SortedCollection. The clue in the sort:to: seems to be that they know they use an array as datastructure, and can use swap and other things.

I made some timings of the two algorithms, and it seems like the #sort:to: is a few (2-3) percent faster, so not really an issue.

My suggestion is to remove the marginally faster algorithm, and make all build-in sorting be based on the algorithm in SequenceableCollection

I tried, and it does not violate any tests.

[kasperosterbye]

It is actually worse than bad.
The implementation used everywhere but in SortedCollection is a conservative sort (keeping equal elements in original order).
The adding of new elements into a SortedCollection is linear (uses insertion by moving existing elements).

However, because the browser - Calypso - depends so strongly on SortedCollection the Pharo system hangs if I try to change anything in SortedCollection.

[guillep]

This is more a discussion than an actionable issue.
Please reopen if you consider there is an objective way to fix it.