# Introduction to Algorithms: Chapter Two, Merge Sort

*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 `p`

s and `q`

s 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:

Recursion is considered both a fundamental precept of computer science and a litmus test that separates the decent programmers from the terrible ones.

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:

defdevcamp_merge_sort(list)

iflist.length <= 1

list

elsemid = (

list.length / 2).floor

left = devcamp_merge_sort(list[0..mid - 1])

right = devcamp_merge_sort(list[mid..list.length])

devcamp_merge(left, right)

enddevcamp_merge(

end

defleft,right)

ifleft.empty?

right

elsifright.empty?

left

elsifleft.first <right.first

[left.first] + devcamp_merge(left[1..left.length],right)

else[

right.first] + devcamp_merge(left,right[1..right.length])

endarray = [7, 3, 6, 5, 1, 4]

end

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!