Merge Sort
Mergesort divides the list in half everytime,
calling itself on each half. As the recursion unwinds, it merges the
sorted list into a new
sorted list. For example, assume we have the following:
(mergesort '(6 4 5 7 8 9 3 4))
/ \
(mergesort '(6 4 5 7)) (mergesort '(8 9 3 4))
/ \ / \
(mergesort '(6 4)) (mergesort '(5 7)) (mergesort '(8 9)) (mergesort '(3 4))
At the lowest tree leves, the two element get sorted and the recursion unwinds.
(mergesort '(6 4 5 7 8 9 3 4))
/ \
(mergesort '(6 4 5 7)) (mergesort '(8 9 3 4))
/ \ / \
(4 6) (5 7) (8 9)) (3 4))
The next level of recursion:
(mergesort '(6 4 5 7 8 9 3 4))
/ \
(4 5 6 7)) (3 4 8 9)
/ \ / \
(4 6) (5 7) (8 9)) (3 4))
And the final level with merges into the overall list
(3 4 4 5 6 7 8 9)
/ \
(4 5 6 7) (3 4 8 9)
Of course, this is not the actual order that things happen but it give
the overall algorithm flavor.
In scheme, we can write functions to split lists, and merge sorted
lists. Once we have these, the mergesort itself is fairly short.
def mergesort(lis)
if lis.length == 0 then
[]
elsif lis.length == 1 then
lis
elsif lis.length == 2 then
mergelists ([lis[0]], lis[1..lis.length-1])
else
mergelists(mergesort(split(lis)[0]),mergesort(split(lis)[1..lis.length-1][0]))
end
end
mergelists: m
" assume L and M are sorted lists "
self size = 0 ifTrue:[
^m.]
ifFalse: [
m size == 0 ifTrue: [
^self.]
ifFalse: [
self first < m first ifTrue: [
^(OrderedCollection with: self first),
(self allButFirst mergelists: m).]
ifFalse: [
^(OrderedCollection with: m first),
(self mergelists: m allButFirst).]
]
]
!
sub: start stop: stop counter: ctr
" extract elements start to stop into a list"
self size = 0 ifTrue: [
^self.]
ifFalse: [
ctr < start ifTrue: [
^self allButFirst sub: start stop: stop counter: (ctr+1).
]
ifFalse: [
ctr > stop ifTrue: [
^#() asOrderedCollection.
]
ifFalse: [
^(OrderedCollection with: self first),
(self allButFirst sub: start stop: stop counter: (ctr+1)).
]
]
]
!
split
" split the list in half:, ; returns ((first half)(second half)) "
| length |
length := self size.
length = 0 ifTrue: [
^(OrderedCollection with: self), (OrderedCollection with: self).
]
ifFalse: [
length = 1 ifTrue: [
^(OrderedCollection with: self),
(OrderedCollection with: #() asOrderedCollection).
]
ifFalse: [
^(OrderedCollection with:
(self sub: 1 stop: length/2 counter: 1)),
(OrderedCollection with:
(self sub: (length/2 + 1) stop: length counter: 1)).
]
]
!
x = [6,3,4,9,10,1,7]
print x, "\n"
#print split(x)
print mergesort(x), "\n"