Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.465.mcz

==================== Summary ====================

Name: Collections-ul.465
Author: ul
Time: 13 November 2011, 5:18:00.299 am
UUID: 49a23071-1538-2b44-be74-cf1f2dc81fc9
Ancestors: Collections-eem.464

Improved quicksort by another ~5% (when the receiver is an Array of SmallIntegers) by simplifying swaps, avoiding popIntoTemp: and reordering temporaries.

=============== Diff against Collections-eem.464 ===============

Item was changed:
  ----- Method: ArrayedCollection>>quickSortFrom:to:by: (in category 'sorting') -----
  quickSortFrom: from to: to by: sortBlock
  	"Sort elements i through j of self to be nondescending according to sortBlock using an in-place quicksort with simple median-of-three partitioning with guaranteed O(log(n)) space usage."
  
+ 	| dij k l temp i j di dj n ij |
- 	| i j |
  	i := from.
  	j := to.
  	[
+ 		
- 		| k l dij temp ij di dj n |
  		"The prefix d means the data at that index."
  		"Sort di,dj."
  		di := self at: i.
  		dj := self at: j.
  		(sortBlock ifNil: [ di <= dj ] ifNotNil: [ sortBlock value: di value: dj ]) ifFalse: [
+ 			self at: i put: dj; at: j put: di. temp := dj. dj := di. di := temp "swap di with dj" ].
+ 		(n := j + 1 - i) <= 2 ifTrue: [ ^self ].
- 			temp := self at: i. self at: i put: (self at: j); at: j put: temp.
- 			temp := di. di := dj. dj := temp ].
- 		(n := j + 1  - i) <= 2 ifTrue: [ ^self ].
  		"More than two elements."
+ 		dij := self at: (ij := i + j // 2). "ij is the midpoint of i and j. Sort di,dij,dj. Make dij be their median."
- 		ij := (i + j) // 2.  "ij is the midpoint of i and j."
- 		dij := self at: ij.  "Sort di,dij,dj.  Make dij be their median."
  		(sortBlock ifNil: [ di <= dij ] ifNotNil: [ sortBlock value: di value: dij ])
  			ifTrue: [
  				(sortBlock ifNil: [ dij <= dj ] ifNotNil: [ sortBlock value: dij value: dj ]) ifFalse: [
+ 					 "swap dij with dj, we don't need the value of the variable dj anymore"
+ 					self at: j put: dij; at: ij put: dj. dij := dj ] ]
- 					temp := self at: j. self at: j put: (self at: ij); at: ij put: temp.
- 					dij := dj ] ]
  			ifFalse: [
+ 				 "swap di with dij, we don't need the value of the variable di anymore"
+ 				self at: i put: dij; at: ij put: di. dij := di ].
- 				temp := self at: i. self at: i put: (self at: ij); at: ij put: temp.
- 				dij := di ].
  		n = 3 ifTrue: [ ^self ].
  		"More than three elements."
+ 		"Find k and l such that i<k<l<j and dk,dij,dl are in reverse order. Swap k and l. Repeat this procedure until k and l pass each other."
- 		"Find k>i and l<j such that dk,dij,dl are in reverse order.
- 		Swap k and l.  Repeat this procedure until k and l pass each other."
  		k := i.
  		l := j.
  		[
  			[ k <= (l := l - 1) and: [ 
  				sortBlock ifNil: [ dij <= (self at: l) ] ifNotNil: [ sortBlock value: dij value: (self at: l) ] ] ] whileTrue.  "i.e. while dl succeeds dij"
  			[ (k := k + 1) <= l and: [
  				sortBlock ifNil: [ (self at: k) <= dij ] ifNotNil: [ sortBlock value: (self at: k) value: dij ] ] ] whileTrue.  "i.e. while dij succeeds dk"
  			k <= l ] whileTrue: [ temp := self at: k. self at: k put: (self at: l); at: l put: temp. ].
  		"Now l<k (either 1 or 2 less), and di through dl are all less than or equal to dk through dj. Sort the larger segment in this method and call another quicksort for the smaller segment. This ensures O(log(n)) space usage."
  		i < l 
  			ifFalse: [
  				k < j
  					ifFalse: [ ^self ]
  					ifTrue: [ i := k ] ]
  			ifTrue: [
  				k < j
  					ifFalse: [ j := l ]
  					ifTrue: [
  						l - i <  (j - k)
  							ifTrue: [ 
  								self quickSortFrom: i to: l by: sortBlock.
  								i := k ]
  							ifFalse: [
  								self quickSortFrom: k to: j by: sortBlock.
  								j := l ] ] ] ] repeat!