Merge Sort
Yesterday I decided to read up on sorting algorithms, a topic I’d previously assumed would be over my head. It turns out I was completely wrong, and I had a lot of fun writing my own merge sort algorithm!
def merge(a,b)
sorted_list=[]
while !a.empty? && !b.empty?
if a.first < b.first
sorted_list << a.shift
elsif a.first > b.first
sorted_list << b.shift
elsif a.first==b.first
sorted_list< < a.shift
b.shift
end
end
((sorted_list<<a)<<b).flatten!
end
def sort(list)
if list.length <=1
return list
else
middle = (list.length/2)-1
a=list[0..middle]
b=list[middle+1..list.length]
merge(sort(a),sort(b))
end
end
How does it work?
Mergesort can be broken down into two parts, which are here divided into two different methods.
The merge method accepts two ordered lists, and combines them into one ordered list by comparing the first value of each of these two input lists and sequentially moving the lower value into a new list:
But if all we have is one unordered list which needs to be sorted, how will a method requiring two ordered lists help us? If we had two ordered lists that each contained half of the numbers of the original list, we could merge the two together to create one ordered list. We can start by breaking our single unordered list in half at the center of the list. Now have two unordered lists half the length of the original, but what we want is two ordered lists. We are faced with the same problem as before: our two unordered lists could be ordered if only we had two smaller ordered lists. If we continue to halve our lists further and further, we can eventually isolate each element of our large unsorted list, resulting in many lists containing only one element. A list containing only one element is inherrently ordered, so once we have broken down our original list to this level, we can begin to merge our many little lists back together.
The process of splitting the unsorted list in half recursively is very similar to a binary tree. In terms of the call stack, the mergesort algorithm decends all the way down each branch of the tree, one at a time, splititng lists at nodes as necessary. Although the original unsorted list is immediately split, the second resultant half-list isn’t touched again until sorting of the first half-list is complete, which may require further splitting, decending and merging. This is because of the way sort is recurssively called within itself: merge(sort(a),sort(b)), where sort(a) must be complete before sort(b). List a is now the input list being passed to sort(), and is itself split into component lists a and b, on which sort(a) and sort(b) will be called yet again. The recursive call is not executed when the length of the input list is 1 and cannot be split any further, at which point we move up a level in the call stack and either descend down another branch to sort another list, or merge two lists together. You can see this demonstrated in the following animation:
Building mergesort was easier than I’d expected but still a fun challenge. I hope to write out the code for some of the other sort algorithms in the coming week.