Daniel Irvine on building software

# Merge sort kata in Clojure

31 May 2015

Watch a recorded video performance of this kata here.

The merge sort algorithm is logically complex and yet quite simple to implement. It makes a good candidate for a TDD kata because the algorithm can be built up without any large jumps in functionality. But if you hope to build it piece-by-piece you need to be careful about the order in which you write your tests. This post is a walkthrough for implementing a basic merge sort algorithm. As a kata, this can be done in under 10 minutes.

I’m using Clojure but you can apply the same tests and implementation to any language.

All sort algorithm katas start with a test for sorting nothing.

``````(ns merge-sort.core-spec
(:require [speclj.core :refer :all]
[merge-sort.core :refer :all]))

(describe "merge-sort"
(it "sorts nothing"
(should= [] (merge-sort [])))
``````

The purpose of the “sorts nothing” test is to get the function signature in place. It doesn’t take much to make this pass in Clojure.

``````(ns merge-sort.core)

(defn merge-sort [input]
[])
``````

Next up is the test for sorting just one number. In TDD parlance we talk about working from the most degenerate case upwards, and sorting one number is the next obvious case up from sorting no numbers.

``````(it "sorts one"
(should=  (merge-sort )))
``````

Although it might seem like an uninteresting change, implementing this actually gives us the terminating case for the forthcoming recursion.

``````(defn merge-sort [input]
input)
``````

Let’s move on to actually sorting something.

``````(it "sorts two things"
(should= [2 3] (merge-sort [3 2])))
``````

Implementing this requires a conditional:

``````(defn merge-sort [input]
(if (< 1 (count input))
[(second input) (first input)]
input)
``````

Here we see the emergence of the merge process. The merge sort algorithm has two main steps:

1. A divide-and-conquer step where the list is split in half and each half is sorted, and
2. A merge step where two already sorted lists are merged by iterating through both lists in tandem, at each step selecting the minimal element for the resulting list.

In the simplest form of merge sort, the input list is continually halved in size, and then halved again and again, until eventually we end up with two 1-item lists to be merged, which is the trivial case that we are now implementing through the test above and the test about to follow.

``````(it "merges two halves of a sorted 2-item list"
(should= [2 3] (merge-sort [2 3])))
``````
``````(defn merge-sort [input]
(if (< 1 (count input))
(if (< (second input) (first input))
[(second input) (first input)]
[(first input) (second input)])
input)
``````

That seems good enough for lists of 1 or 2 items. Now let’s move on to dealing with 3-item lists.

``````(it "merges sorted halves"
(should= [2 3 4] (merge-sort [3 4 2])))
``````

It’s important that this particular test uses a 3-item list that can be split into two already sorted halves because we aren’t yet recursively sorting. This test above for `[3 4 2]` will end up merging the two lists `[3 4]` and ``, both of which are already sorted. A subsequent test will use `[4 3 2]` which will force a different part of the algorithm to be developed.

This seems like a good time to extract a `merge-list` method before we extend it. So let’s pend the test we just wrote.

``````(xit "merges sorted halves"
(should= [2 3 4] (merge-sort [3 4 2])))
``````

Extracting a `merge-list` function gives us:

``````(defn- merge-list [a b]
(if (< b a)
[b a]
[a b]))

(defn merge-sort [input]
(if (< 1 (count input))
(merge-list (first input) (second input))
input))
``````

Once we see the original tests passing with this refactored code, we can then re-enable the 3-item list test:

``````(it "merges sorted halves"
(should= [2 3 4] (merge-sort [3 4 2])))
``````

The new `merge-list` function must be rewritten to iterate over each list element in turn, rather than simply dealing with one element. The function signature will change to take two lists, `as` and `bs`, instead of the previous implementation’s two single values, `a` and `b`.

``````(defn- merge-list [as bs]
(if (< (first bs) (first as))
(cons (first bs) as)
(cons (first as) bs)))

(defn merge-sort [input]
(if (< 1 (count input))
(apply merge-list (split-at (/ (count input) 2) input))
input))
``````

Note the new call to `apply merge-list` which uses `split-at`.

This implementation of `merge-list` works for the 3-item list we’ve supplied, but anything larger will blow up.

``````(it "merges four things"
(should= [2 3 4 6] (merge-sort [4 6 2 3])))
``````

We need to make `merge-list` call itself recursively.

``````(defn- merge-list [as bs]
(cond
(empty? as) bs
(empty? bs) as
:else
(if (< (first bs) (first as))
(cons (first bs) (merge-list as (rest bs)))
(cons (first as) (merge-list (rest as) bs)))))
``````

The final step then is to ensure that each merged list is itself sorted. Let’s write a test for this. We can go back to using a 3-item list for this, this time with `[4 3 2]` as I mentioned earlier.

``````(it "sorts three things"
(should= [2 3 4] (merge-sort [4 3 2])))
``````

This is very simple to implement, with an addition of a call to `map merge-sort`.

``````    (apply merge-list (map merge-sort (split-at (/ (count input) 2) input)))
``````

And with that, all that remains is to verify that this works for a large data set.

``````(it "sorts a lot"
(should= (range 0 1000) (merge-sort (shuffle (range 0 1000))))))
``````

It’s worth pointing out that the implementation of `merge-list` above is not tail-recursive and is therefore at risk of stack overflow. It’s left as an exercise to the reader to rewrite this function using `loop-recur`. 