I would be interested in improvements. This is just a straight translation
of the java code.
Yaroslavskiy's Dual-Pivot Quicksort seems to perform better for large
collections:
A straightforward
defaultSort: i to: j
self dualPivotQuicksort: i to: j split: 3
dualPivotQuicksort: left to: right split: div
|len third m1 m2 pivot1 pivot2 less great dist newDiv|
len := right - left.
newDiv := div.
len < 27 ifTrue: [
left+1 to: right do: [ :i | | j |
j := i.
[(j>left) and: [(array at:j) < (array at: (j-1))]]
whileTrue: [
array swap: j with: j-1.
j := j-1]]]
ifFalse: [
third := len // div.
m1 := left+third.
m2 := right-third.
m1 <= left ifTrue: [m1 := left+1].
m2 >= right ifTrue: [m2 := right-1].
(array at: m1) < (array at: m2) ifTrue: [
array swap: m1 with: left.
array swap: m2 with: right]
ifFalse: [
array swap: m1 with: right.
array swap: m2 with: left].
pivot1 := array at: left.
pivot2 := array at: right.
less := left+1.
great := right-1.
less to: great do: [ :k |
(array at: k) < pivot1 ifTrue: [
array swap: k with: less.
less := less+1.]
ifFalse: [
(array at: k ) > pivot2 ifTrue: [
[(k < great and: [(array at: great) >
pivot2])] whileTrue: [
great := great -1].
array swap: k with: great.
great := great-1.
(array at: k) < pivot1 ifTrue: [
array swap: k with: less.
less := less+1]
]
]].
dist := great-less.
dist < 13 ifTrue: [ newDiv := div+1].
array swap: (less-1) with: left.
array swap: (great+1) with: right.
self dualPivotQuicksort: left to: (less-2) split: newDiv.
self dualPivotQuicksort: (great+2) to: right split: newDiv.
(dist > (len -13) and: [ pivot1 ~= pivot2]) ifTrue:[
less to: great do: [ :k |
(array at: k) = pivot1 ifTrue: [
array swap: k with: less.
less := less+1]
ifFalse: [
(array at: k) = pivot2 ifTrue: [
array swap: k with: great.
great := great - 1.
(array at: k) = pivot1 ifTrue: [
array swap: k with:
less.
less := less+1]
]
]
]
].
pivot1 < pivot2 ifTrue: [
self dualPivotQuicksort: less to: great split: newDiv]
]
Do we have a performance test set for sorting?
