Stable sort

[Olli Pietiläinen]

Hi.

Attached is stable sort, adapted from squeak. It uses merge-sort algorithm.
I think it'd be worthwhile to have also stable sort in the library. Feel
free to make corrections if needed.


Olli
-------------- next part --------------
s@(Sequence traits) stableSortFrom: start to: end by: block
"Perform a stable sort (using merge-sort algorithm) within the 
start/end bounds using the sort block."
[| middle scopy i1 i2 val1 val2 out |
 s size <= 1 ifTrue: [^ s].
 end > s size ifTrue: [end: s size].
 start >= end ifTrue: [^ s].
 middle: (start + end) // 2.
 scopy: s copy.
 scopy stableSortFrom: start to: middle by: block.
 scopy stableSortFrom: middle + 1 to: end by: block.
 i1: start.
 i2: middle + 1.
 val1: (scopy at: i1).
 val2: (scopy at: i2).
 out: start - 1.
 [(i1 <= middle) /\ [i2 <= end]] whileTrue:
   [(block applyWith: val1 with: val2)
      ifTrue: [s at: (out: out + 1) put: val1.
	       val1: (scopy at: (i1: i1 + 1))]
      ifFalse: [s at: (out: out + 1) put: val2.
		i2: i2 + 1.
		i2 <= end ifTrue: [val2: (scopy at: i2)]]].
 i1 <= middle 
   ifTrue:  [s replaceFrom: out + 1 to: end with: scopy startingAt: i1]
   ifFalse: [s replaceFrom: out + 1 to: end with: scopy startingAt: i2]
].

s@(Sequence traits) destructiveStableSortBy: block
[
  s stableSortFrom: 0 to: s indexLast by: block
].

s@(Sequence traits) destructiveStableSort
[
  s destructiveStableSortBy: [| :a :b | a <= b]
].