# Coding Challenge: Implementing MergeSort in Ruby

Lately I've been trying to challenge myself by taking a stab at some common coding questions asked in software engineering job interviews. After years of working on apps you would think that this kind of thing comes easy, but software development in the modern age comes with a heavy side of Googling and lookup, so challenging your brain in this way to come up with or code an algorithm or process from scratch without that assistance is good practice to keep you sharp.

Previously, I had come up with three solutions of finding a missing number in array of 1 through 100, and today, after reintroducing myself to the algorithm, I am going to implement a O(N) search method: MergeSort.

I'll present all code in this post as easy-to-read
`Ruby`

code, and
I will also try to avoid some of the obscure language shortcuts to make the
method more clear.

In order to implement an algorithm in any language, you need to understand it, so here is where I needed to lookup how MergeSort works:

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. GeeksforGeeks

Sounds simple enough. Looking through the many different implementations in other languages around the web, it can get trickier if you are trying to do everything in constant memory, or if you are working within a language which makes you define array lengths beforehand. I'm not going to worry about that here. I'm only going to implement the logic based on the algorithm.

First, let's define a recursive method to call and setup a simple test to see if it is working:

Obviously, this will fail. Running it produces our failure output:

Now that we have a basic test for success, we can begin, starting with
*"It divides input array in two halves, calls itself for the two halves"*. While this is the majority of the algorithm's description above, it's
actually the uninteresting part. After determining the half size of the array,
I'll use
`take`

and
`drop`

to split them, them call a new (unwritten) method to merge them correctly.

But, because this is a recursive function, we need a stop condition.
`merge_sort`

returns an array of sorted values, and it doesn't
really need to concern itself with how the order is, so the only stop
condition is when we have an array that is too small to sort. This works
because as we keep dividing and dividing the array in to subarrays and
subarrays, we will eventually get to a place where
`merge_sort`

is asked to sort an array of length 1. When this happens, we just return the
already sorted array. Otherwise, we return the merged array as above. Adding
this to the method:

Defining our `merge`

function with some basic (incorrect) code, we
can run the test again.

There is no change, as expected. What we have done so far is recursively
broken this array up into 10 different subarrays of length 1, then combined
them all through simple concatenation, leaving us with the original sequence.
Let's get down to the interesting part of the written algorithm above:
*"and then merges the two sorted halves"*.

To merge these arrays, we need to realize that they are already sorted. This
is the contract we have with the
`merge_sort`

algorithm. We are only expected to merge two already sorted arrays in this method. At the base
case, we would be asked to merge two arrays of count 1 (eg:
`[3]`

,
`[7]`

), but it will eventually have to merge sorted arrays of size
`array.size / 2`

(eg:
`[1, 3, 4, 8, 9]`

,
`[2, 5, 6, 7, 10]`

). Because these are already sorted, we only need
to compare the left-most values of each array with one another, and choose the
lowest one to put into a new array. We repeat until we have placed all items
from both arrays. The pseudocode looks something like this

After the while block, we can be sure that either
`array1`

or
`array2`

is empty, so we can just add the rest on top, in order, as
they are all larger than the last element in the array. The real code looks
like this:

This works because
`push`

adds an element to the end of an array,
`shift`

pops it off the front, and
`+=`

will return the
original array when passed an empty one. Putting everything together we have:

And finally running our test, we see success:

And to make sure it works for larger arrays, let's try one with 1000 numbers

There are some improvements that could be made to increase efficiency, such as not creating new arrays but rather manipulate original ones, but I'll leave that for another day.

Was this page helpful for you? Buy me a slice of 🍕 to say thanks!

## Comments