'From Cuis 2.5 of 9 August 2010 [latest update: #534] on 10 August 2010 at 10:12:56 am'!

!Collection methodsFor: 'sorting' stamp: 'ul 3/22/2010 12:13'!
sorted: aSortBlockOrNil
	"Return a new sequenceable collection which contains the same elements as self but its elements are sorted by aSortBlockOrNil. The block should take two arguments and return true if the first element should preceed the second one. If aSortBlock is nil then <= is used for comparison."

	^self asArray sort: aSortBlockOrNil! !


!ArrayedCollection methodsFor: 'sorting' stamp: 'ul 11/2/2009 03:26'!
mergeFirst: first middle: middle last: last into: dst by: aBlock
	"Private. Merge the sorted ranges [first..middle] and [middle+1..last] 
	of the receiver into the range [first..last] of dst."

	| i1 i2 val1 val2 out |
	i1 := first.
	i2 := middle + 1.
	val1 := self at: i1.
	val2 := self at: i2.
	out := first - 1.  "will be pre-incremented"

	"select 'lower' half of the elements based on comparator"
	[ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: 	[
		(aBlock 
			ifNil: [ val1 <= val2 ]
			ifNotNil: [ aBlock value: val1 value: val2 ])
				ifTrue: [
					dst at: (out := out + 1) put: val1.
					val1 := self at: (i1 := i1 + 1)]
				ifFalse: [
					dst at: (out := out + 1) put: val2.
					(i2 := i2 + 1) <= last ifTrue: [
						val2 := self at: i2 ] ] ].

	"copy the remaining elements"
	i1 <= middle
		ifTrue: [dst replaceFrom: out + 1 to: last with: self startingAt: i1]
		ifFalse: [dst replaceFrom: out + 1 to: last with: self startingAt: i2]! !

!ArrayedCollection methodsFor: 'sorting' stamp: 'ul 11/2/2009 04:56'!
sort
	"Sort this array into ascending order using the '<=' operator."

	self sort: nil! !


!Array methodsFor: 'sorting' stamp: 'ul 3/22/2010 12:16'!
sorted: aSortBlockOrNil
	"Return a new sequenceable collection which contains the same elements as self but its elements are sorted by aSortBlockOrNil. The block should take two arguments and return true if the first element should preceed the second one. If aSortBlock is nil then <= is used for comparison."
	
	^self copy sort: aSortBlockOrNil! !


!OrderedCollection methodsFor: 'adding' stamp: 'ar 7/15/2008 23:03'!
add: newObject afterIndex: index 
	"Add the argument, newObject, as an element of the receiver. Put it in 
	the sequence just after index. Answer newObject."
	(index between: 0 and: self size) ifFalse:[^self errorSubscriptBounds: index].
	self insert: newObject before: firstIndex + index.
	^ newObject! !

!OrderedCollection methodsFor: 'adding' stamp: 'ar 7/15/2008 23:05'!
add: newObject beforeIndex: index 
	"Add the argument, newObject, as an element of the receiver. Put it in 
	the sequence just before index. Answer newObject."
	(index between: 1 and: self size+1) ifFalse:[^self errorSubscriptBounds: index].
	self insert: newObject before: firstIndex + index - 1.
	^ newObject! !

!OrderedCollection methodsFor: 'sorting' stamp: 'ul 11/2/2009 04:56'!
sort
	"Sort this array into ascending order using the '<=' operator."

	self sort: nil! !

!OrderedCollection methodsFor: 'sorting' stamp: 'ul 11/2/2009 05:18'!
sort: aSortBlock 
	"Sort this collection using aSortBlock. The block should take two arguments
	and return true if the first element should preceed the second one.
	If aSortBlock is nil then <= is used for comparison."

	self ifNotEmpty: [
		array
			mergeSortFrom: firstIndex
			to: lastIndex
			by: aSortBlock ]! !

!OrderedCollection methodsFor: 'sorting' stamp: 'ul 3/22/2010 12:16'!
sorted: aSortBlockOrNil
	"Return a new sequenceable collection which contains the same elements as self but its elements are sorted by aSortBlockOrNil. The block should take two arguments and return true if the first element should preceed the second one. If aSortBlock is nil then <= is used for comparison."
	
	^self copy sort: aSortBlockOrNil! !

