Introduction to Algorithms: Chapter Two, Merge Sort

Amber Wilkie
Jan 31, 2017 · 5 min read

Come with me on a walk through Introduction to Algorithms by Cormen, et al., referred to on the internet as the “bible” of algorithms. Start at the beginning here.

Insertion Sort went pretty well! Onto merge sort. After some fiddling with it, I got the merge part down. I thought I understood the theory, then I watched this MIT video (thanks MIT!) and the pieces slid into place easily:

Merge sort is a method by which you break an unsorted array down into two smaller halves and so forth until you have a bunch of arrays of only two items. You sort each one, then merge each with another two-item array, then you merge the four-item arrays and so on all the way back up to a fully sorted array.

Great! The pseudocode looks like this (much abbreviated, I’ll give more detail below). Initial input is p = 0 and r = Array.index(Array.last) . (Also, my apologies if that is a really sloppy way to find the last index in an array).

Merge-Sort(Array, p, r)
if p < r
q = (p + r)/2
Merge-Sort(Array, p, r)
Merge-Sort(Array, q + 1, r)
Merge(Array, p, q, r)
Merge(Array, p, q, r)
// Split the array, merge the two together.

So what’s happening? It’s a little hard to see with the different ps and qs floating about, but we take the array, cut it in half, then send both halves back through the merge-sort. So merge-sort breaks the arrays down into the small pieces we need, then merge sorts them. Sounds great. My merge function at this point was doing exactly what it was supposed to do — taking a two-item array and sorting it, or taking two sorted arrays, joined, them merging them. But something terribly wrong was happening in the recursive part. Time to dig in deeper…

Recursion in Ruby

The first link I hit trying to study up on recursion in Ruby had this withering text as its first line:

Well gosh, now I have to figure this out.

The short answer is that a recursive method calls itself. So this is a recursive method:

def recurse
recurse
end

Of course, this method will give you “stack overflow” — that is, it will just go on forever and ever and ever. It’s the same as

loop do
end

Nothing to do, nowhere to go, the method will just run forever until your computer melts.

So one critical element in a recursive function is that it must contain some kind of stop — a point at which it will quit calling itself. For our means in this merge sort, we’ll need to break our array down into individual numbers and then stop. We’ll do that by telling our method to quit working when it gets to array.length == 1.

How Recursion Works in Ruby

Our method above is somewhat complex, actually. The theory is simple but the execution requires multiple calls back up to see what is really going on. Here’s an extremely simple example:

def recurse(num)
if num > 0
num -= 1
puts "in if: #{num}"
recurse(num)
end
puts "out if: #{num}"
end

If we run that, we get the output to the left. As you can see, we hit the if statement twice before we get to the rest of the recurse method. When we get to the recurse(num) call, we jump back up to the top and start over, ignoring what is in the rest of the method.

But here’s the interesting part, we actually get to the out if three times, not once. Twice because we call the recurse(num) from inside our if statement and once for the initial call that we made “manually”. Further, we go down into the recursion, but out by the same way but in the opposite direction. Look — we start with num == 1, then deal with some zeroes, then it goes back to one.

Finally, we can start to make sense of this stuff! If we can reduce those arrays to individual items, then pass them in two at a time to a merge method, we’ll ultimately be coming back up through the process on the way out of our method — we’ll get to call our merge method after all of our recursive calls, but we get to run it on the results of those calls after the recursive methods run. Cool, right?

Now back to the code

Trust me, I did not figure out that recursion thing first. After ages of thinking about it and trying to follow the rabbit down the argument-input hole, I gave up and found a site that had done it for me. Thank you very much DevCamp, because your code finally worked and I could start playing with it and really understanding what the hell is going on!

Here it is:

def devcamp_merge_sort(list)
if list.length <= 1
list
else
mid = (list.length / 2).floor
left = devcamp_merge_sort(list[0..mid - 1])
right = devcamp_merge_sort(list[mid..list.length])
devcamp_merge(left, right)
end
end

def
devcamp_merge(left, right)
if left.empty?
right
elsif right.empty?
left
elsif left.first < right.first
[left.first] + devcamp_merge(left[1..left.length], right)
else
[right.first] + devcamp_merge(left, right[1..right.length])
end
end
array = [7, 3, 6, 5, 1, 4]
devcamp_mergesort(array)

Phew!

Our computer is going to split our array, assign half to left and the other half to right, then it has to go right back up and try again, again splitting in half. And it will do this until the list.length <= 1. Now all those recursive calls are stacked up, ready to be dealt with one by one back on “down” the list with merge until we are back at the full length of the array.

Still confused? No worries, I didn’t make sense of this until I started writing about it. Try this link for more excellent examples.

Recursion is one of those things you have to keep thinking about for a long time, I surmise. In the meantime, I’ve burned two days on this and I’m only halfway through Chapter Two… until next time!

Craft Academy

Bringing the craft of coding to a broad public — bootcamp…