# Implementing mergesort in Ruby

*NB* I’ve been a mostly self-taught programmer since I was in middle school (about 20 years now). I’m in the processing of teaching myself some of the things I missed out on by not having a Computer Science education; I’m also new to Ruby. This post is me writing out my thoughts on this subject to better understand it for myself — maybe someone else will find it useful, but don’t mistake me for an expert.

Mergesort is a classic “divide and conquer” algorithm for sorting an array. We have a problem like this:

**Input:**An unsorted array of numbers, e.g.`[1, 4, 3, 9]`

.**Output:**The input array, sorted from least to greatest, e.g.`[1, 3, 4, 9]`

.

Mergesort works by splitting the input array into progressively smaller sorted arrays and then merging those sorted arrays together to produce the final sorted array.

Here is an implementation of mergesort I wrote in Ruby. I’ll break it down in the rest of this post.

Mergesort is split into two functions: a function `mergesort`

which splits the array into smaller pieces and calls the `merge`

function on those smaller pieces, and another function, the `merge`

function, which combines two already-sorted arrays into a single sorted array.

Let’s look at the `merge`

function first.

The merge function takes two arrays, `left`

and `right`

, as parameters. It goes through each array element by element comparing them — if the `left`

array’s element is smaller, it takes that element from the `left`

array and adds it to a new `sorted`

array; then it compares the next `left`

element with the same `right`

element. It does this until both `left`

and `right`

arrays are empty, then returns the `sorted`

array.

If I pass `merge([9], [1])`

it returns `[1, 9]`

.

Passing `merge([0, 2], [1, 3])`

returns `[0, 1, 2, 3]`

.

Passing `merge([9, 1], [2, 3])`

, though, returns `[2, 3, 9, 1]`

because `merge`

isn’t a sorting algorithm on its own — it just merges together two already-sorted arrays. We need to pass `merge`

already-sorted arrays in order for it to work.

The function `mergesort`

does that by splitting the input array into successively smaller arrays, splitting the input array in half and recursively calling itself on the two halves until it reaches two arrays of size 1^{1}. Once it has two arrays of size 1, it calls `merge`

on those two arrays and starts building up a single sorted array out of progressively larger sorted array inputs.

Adding some output to the program shows what’s going on a little more clearly.

Running that outputs:

You could visualize it like this:

I hope that makes things clear! I think I will save analyzing the runtime complexity^{2} or discussions of when to use mergesort versus other sorting algorithms as exercises for the reader, or maybe future blog posts.

# Footnotes

^{1} Assuming an initial input array of size 2 or more — otherwise it would just return its input.

^{2} The diagram above would be a good starting point.