# Sorting Kata - Merge Sort

In the setup we created a solution with two projects. The purpose of these two projects was for a Sorting Kata.

In Linq OrderBy we added a Bookshelf class to hold our sorting methods.

In List Sort we used the built-in sort method of a list. This required us to implement IComparable in the Book class.

In Bubble Sort we overloaded the < and > operators so that books could be sorted through a simple sort.

Here is our Book class.

Now we are going to write our own Merge Sort method.

We write a failing test first.

We use CTRL+. to add the MergeSort method that accepts the list of books. Our goal is for the method to return a sorted list. Then we can assert that the correct book appears first.

Running the test causes the following error:

1 test failed: System.NotImplementedException

Hurray, the test failed. We use the Red, Green, Refactor pattern from Kent Beck's book, Test Driven Design By Example.

The problem is, it failed for the wrong reason. We want to see a failure because the books are not sorted. Let's take a look at the Bookshelf class.

Well, that explains our "NotImplementedException".

So, what is it going to take to get this test to fail for the right reason? Let's take a look at Uncle Bob's Transformation Priority Premise. The first transformation we should try is "nil". Can we get the test to fail by doing nothing? No, our code will not compile unless we return something. The next step is a constant. Let's just return the books list as is.

1 test failed Expected: Partnoy, Frank. Wait: The Art and Science of Delay But was: Watt, Andrew. Beginning Regular Expressions

In Linq OrderBy we overrode the Book.ToString() to get the author and title.

We saw a failing test (Red), and we made sure the message was helpful. Now we can make it green.

The Merge Sort algorithm defined on Sorting-Algorithms.com is:

This is a big one. So far our sorts have dealt with taking a single book off the shelf and bubbling it up to the top, inserting it, or selecting it for placement. Up until now it would be (with a little practice) easy to understand what each algorithm is doing.

With merge sort I really had to do some investigation. I read other websites, and I even watched a great YouTube video on it. I finally understand what it is doing.

Another difficult thing we encounter is recursion. It's a good thing we have been doing our Recursion Kata.

Let's translate this into C#. Instead of b, i, k, and n, I'm going to give the variables longer names.

## Variables

We used a lot of variables in this algorithm.

We stored the count of books in the bookCount variable. Each time we recursively call the method, the count gets smaller. Once it reaches less than two, we return. This if statement keeps from infinitely looping.

Next, we split the books into two piles. The index of the middle is stored in a variable. We will use this to divide the piles of books and go through each pile.

We have a firstHalf and a secondHalf of books. Each gets merge sorted until we are comparing only one book. Eventually, the reoccurrence stops and we continue below the recursion to actually compare books.

We initialize three index variables:

- firstHalfIndex keeps track of where we are in the first half of the books.
- secondHalfIndex keeps track of where we are in the second half of the books.
- finalIndex keeps us moving through each book in both stacks.

## First Loop

In the first loop we look at every book from both piles and compare them to each other. If the first book from the first pile should come before the first book in the second pile, we place the first pile book into our final, sorted list. We increment the first and final indexes so that we keep moving through the pile.

If the first book from the first pile should come after the first book in the second pile, we place the second pile book into our final, sorted list. We increment the second and final indexes so that we keep moving through the pile.

## Additional Loops

At the end of the first loop we might have some books left over in either the first or second pile. We put these left over books on the end of the final, sorted book list.

Finally, we return the sorted list.

When we run the test we see:

1 test passing

## Conclusion

I recommend setting a breakpoint and watching the list of books change order.

Please contact me about this Kata. I would love to get your feedback.