Red Green Repeat Adventures of a Spec Driven Junkie

Mergesort with Tests

Why??

Mergesort is a classic sorting algorithm that has been implemented endlessly. Why implement it again? To hone my thinking, algorithm, and development skills! Reworking classic algorithms are a great way to do this.

Doing the algorithms course a second time brought back a lot of feelings (most good!) but this time I am developing the algorithms using test driven development. This is how I figured out to do Dead Simple Tests since I just wanted to get testing fast.

I definitely enjoyed implementing mergesort in Ruby using tests and this is kind of my thought process as a I went through implementing mergesort (with some commentary.)

Mergesort is a recursive algorithm which divides the input in half each time. Those are sorted individually and the result is merged back. Hence, the name ‘mergesort’. If you want more details, I also used this article but there are many more resources.

Testing strategy

Even with tests, there are a couple of ways to approach this, but I took the inside-out approach since I had a good idea of what the algorithm is doing and that seemed more complex to me than going outside-in (i.e. from reading in the file first.) I wanted to do the ‘hard work’ on the inside of the algorithm first, then worry about outside of the algorithm. The end result is the same, and basically tests are interchangable at the end. Either approach is fine but I want to frame the following tests.

Note: I will only present the tests I used with an explanation (since Mergesort code can be found everywhere)

First test

I’m always a bit apprehensive when starting out a recursive algorithm. I always dread the stack too deep error from Ruby. So, with tests, I will start with the base case. The base case of mergesort is an array of a single element. A single element array is always sorted, so let’s start with those tests:

1

puts mergesort([1]) == [1]

Even by just doing this, there’s a few questions that come up:

  • Is our test suite working?
  • What does the method look like?
  • What are the arguments into the method?
  • What’s the method’s output?

Here, I’m using a very basic test, but it’s always good to make sure your test suite is hooked up properly, no matter the testing framework. In terms of what the method looks like, Mergesort really just takes one argument and calling it mergesort seems very sensible. Input arguments to mergesort will just be an array (since Mergesort algorithm description says the method will call itself).

A quick way to get started and make this test pass:

1
2
3

def mergesort(array)
  array
end

It’s a bit of a shortcut and even I do this time to the time because it helps me move fast and honestly, I just want the first test to pass most reliably and with the least amount of code. Anything more at this point is overly complicated. The most important part about this first test are answering those four questions asked.

Next test

For the next test, let’s add an element:

1

puts mergesort([1,2]) == [1,2]

The first set of tests will still pass and the easy implementation will pass this. This isn’t so important now but it will be as the implementation change further along. I like to think of this case as a sorted base case.

Test which take some work

Up to now, the tests can all just be passed with a trivial implementation. With the next test, let’s make the implementation do some work to make sure the test pass:

1

puts mergesort([2,1]) == [1,2]

Now, the first implementation won’t make this test pass and there needs to be some work done. (I won’t describe those details here, but you’re smart enough to complete this. ;-) ) The implementation will start to recurse with half the elements and do some merging. Some pseudocode to make this pass:

1
2
3
4
5
6
7
8

def mergesort(array)
  left = array.first
  right = array.last
  left_sorted = mergesort(left)
  right_sorted = mergesort(right)

  merge(left_sorted, right_sorted)
end

A new method

Now with the last test, a new method is introduced: merge. I can make the argument that this is a private method to mergesort and does not need to be tested. That would be perfectly valid and I would leave it.

Since we are doing an exercise, I want to make my debugging a bit easier by testing out merge as well, and well, merge is where a lot of the magic happens in mergesort.

These are the tests for merge:

1
2
3
4
5
6
7

left = [1]
right = [2]
puts merge(left, right) == [1,2]

left = [2]
right = [1]
puts merge(left, right) == [1,2]

Testing out everything as finely as possible is important. When I have to look through code and debug methods, I can be confident how each part acts (and run the tests again to make sure they act that way.)

Using built-in methods

The next tests I added were:

1
2
3
4
5
6
7

array = Array(1..3).reverse!
puts mergesort(array) == array.sort

# and the tests for merge:
left = [2,3]
right = [1]
puts merge(left, right) == Array(1..3)

This is exactly the same as the previous array, but I’m using Ruby’s built-in Array.reverse! method to generate my test. This is the same as: [3,2,1] and well, it’s more typing. On the output as well, I’m using a built-in library to help with generating the correct output. Using the system calls to generate the test as well as generate the correct output will come in handy later on. (BUT don’t use the built in method for the sort!)

This test also introduces an odd sized array, so I have to be careful about splitting the array in half for sorting and the merge. Those off by one errors are tricky to debug.

Now, let’s generate a larger array to test:

1
2

array = Array(1..10).reverse!
puts mergesort(array) == array.sort

Notice, is this basically the same test a before. By using Ruby’s built-in methods, I can generate huge tests and correct output with very little code. If I typed out the same arrays, it would be: [10,9,8,7,6,5,4,3,2,1] and [1,2,3,4,5,6,7,8,9,10]. That would be too easy to ‘fat finger’ and I would have to debug my input and outputs. This saves a lot of headaches around something so simple that Ruby can generate.

Testing different input variants

The next step is to introduce a few variants in the input: what if only one element was misplaced?

1
2
3
4
5

array = [1,6,2,3,4,5]
puts mergesort(array) == array.sort

array = [1,3,4,5,2,6]
puts mergesort(array) == array.sort

I had to use these to make sure I was getting the right output for the homework assignment. ;-)

Edge cases

Now that we have a lot of solid test cases for the happy path, let’s see how we can cover some edge cases:

nil input?

I always hate nil as an input. Nothing stops a system from working like nil. So handling this as a test case is great (and not to mention there’s recursion going on as well!) How should my mergesort handle nil? In these cases, I like to write the test and see how that looks.

1

puts mergesort(nil)

Hmmm… to me, when I see that, I kind of expect an empty array to return. Mainly other inputs always produce an array. So, let’s make that the test:

1

puts mergesort(nil) == []

There’s no right or wrong here, but use some previous examples and what would be expected in the most common situation for the method.

0 as input?

This is similar to the nil case, but now it’s a literal 0, not an [0], which is very different to Ruby. I definitely designed this to just handle arrays, but a single number being passed in is the same as if passing in the base case, but not as array. I’m expecting these to be equivalent:

1

puts mergesort(0) == puts mergesort([0])

So, from the way the tests look, when the input is 0 (or any other numeric) returning [0] makes sense to me.

Other inputs?

Well, so many other things can be passed in to be sorted… and we can just restrict the method to handle arrays and numerics. Test cases like that might be a bit too much to write out, but that would be a very good idea to generate tests for. Just a few:

1
2
3
4
5

hash = { a: 1, b: 2 }
puts mergesort(hash) == []

string = "[1,2,3,4]"
puts mergesort(string) == []

For edge cases, there are some situation where it is clear how those should be handled (i.e. nil input) but for others, it’s not super clear (i.e. literal 0 input). The most important thing is those edge case decisions are captured for another programmer to read the next time this code has to be modified.

File Input

The final step is to read in the file for the assignment! With all the tests in place, I’m confident mergesort will just work. (it’s a good feeling to have confidence in your code!)

Since the mergesort method works on arrays (because that’s how we tested), I want to read the file and process it into an array. I did a basic thing and made sure the method only returned an array, instead of say: File class.

1
2

filename = 'unsorted_array.txt'
puts readFile(filename).is_a? Array

One way to help work with the file reading is to create the file:

1
2
3
4
5
6

test_file = File.new(filename, 'wb')
contents = "1 2 3 4 5"
test_file.write(contents)
test_file.close

puts readFile(filename) == Array(1..5)

This is a great way to manage the file contents as well (very handy when you have to work with different file formats!)

Conclusion

The tests for developing Mergesort has been presented. I really enjoyed developing Mergesort this way. The algorithm itself is very short, but having tests for the base case always helps me get started. Starting small is very good for a recursive algorithm, since the key is in the base case.

Before, I always felt a bit hesitant to implementing an algorithm like Mergesort because I had problems keeping everything in my head. Going back and forth to modifying code as I moved forward in implementation was always stressful since I’m going from working code to broken code. Tests definitely help me manage complexity and my mind is free to focus on getting the failing test(s) to pass: nothing more, nothing less.

Stay testing my friend.