I'm unclear how TDD, the methodology, handles the following case. Suppose I want to implement the mergesort algorithm, in Python. I begin by writing

assert mergesort([]) === []

and the test fails with

NameError: name 'mergesort' is not defined

I then add

def mergesort(a):
    return []

and my test passes. Next I add

assert mergesort[5] == 5

and my test fails with


which I make pass with

def mergesort(a):
    if not a:
        return []
        return a

Next, I add

assert mergesort([10, 30, 20]) == [10, 20, 30]

and I now have to try to make this pass. I "know" the mergesort algorithm so I write:

def mergesort(a):
    if not a:
        return []
        left, right = a[:len(a)//2], a[len(a)//2:]
        return merge(mergesort(left)), mergesort(right))

And this fails with

NameError: name 'merge' is not defined

Now here's the question. How can I run off and start implementing merge using TDD? It seems like I can't because I have this "hanging" unfulfilled, failing test for mergesort, which won't pass until merge is finished! If this test hangs around, I can never really do TDD because I won't be "green" during my TDD iterations constructing merge.

It seems like I am stuck with the following three ugly scenarios, and would like to know (1) which one of these does the TDD community prefer, or (2) is there another approach I am missing? I've watched several Uncle Bob TDD walkthroughs and don't recall seeing a case like this before!

Here are the 3 cases:

  1. Implement merge in a different directory with a different test suite.
  2. Don't worry about being green when developing the helper function, just manually keep track of which tests you really want to pass.
  3. Comment out (GASP!) or delete the lines in mergesort that call merge; then after getting merge to work, put them back in.

These all look silly to me (or am I looking at this wrong?). Does anyone know the preferred approach?

  • 2
    Part of the goal of TDD is to help you create a software design. Part of that design process is discovering what is needed to produce the desired result. In the case of mergesort, since it's already a very well-defined algorithm, this discovery process is not required, and it then becomes a matter of mapping what you already know to be the design to a series of unit tests. Presumably, your top level test asserts that your method under test accepts an unsorted collection and returns a sorted one... – Robert Harvey Nov 9 '16 at 19:30
  • 1
    ...Subsequent unit tests would gradually dig deeper into the actual mechanics of a mergesort. If you're looking for the "right" way to do this, there isn't one, other than to be accurate about your mapping of the mergesort algorithm to a series of unit tests; i.e. they should reflect what a mergesort actually does. – Robert Harvey Nov 9 '16 at 19:30
  • 4
    Design doesn't grow itself from unit tests alone; if you're expecting a mergesort design to emerge naturally from red-green-refactor, that won't happen unless you guide the process based on your existing knowledge of mergesort. – Robert Harvey Nov 9 '16 at 19:36
  • 3
    Heavily recommended: geekswithblogs.net/theArchitectsNapkin/archive/2014/02/10/… – Doc Brown Nov 9 '16 at 20:20
  • 1
    In TDD merge must be invented only on "refactoring" stage. If you see that merge method can be introduced for passing test of mergesort you first make your tests pass without merge method. Then refactor your implementation by introducing merge method. – Fabio Nov 19 '16 at 16:49

Here are some alternative ways to look at your options. But first, the rules of TDD, from Uncle Bob with emphasis by me:

  1. You are not allowed to write any production code unless it is to make a failing unit test pass.
  2. You are not allowed to write any more of a unit test than is sufficient to fail; and compilation failures are failures.
  3. You are not allowed to write any more production code than is sufficient to pass the one failing unit test.

So, one way to read rule number 3 is that you need the merge function to pass the test, so you can implement it -- but only in its most basic form.

Or, alternately, you start by writing the merge operation inline, and then refactor it out into a function after getting the test to work.

Another interpretation is that you're writing mergesort, you know that you'll need a merge operation (ie, it isn't YAGNI, which is what the "sufficient" rule attempts to curtail). Therefore, you should have started with tests for the merge, and only then proceeded to tests for the overall sort.

  • These are really good observations. I had thought of the inline-and-factoring out earlier, but as merge is surprisingly messy, edge-case-wise (as well as useful as a standalone) the idea of doing it as a separate function made more sense. However, the style of doing it inline in its basic form and then factoring it out at the blue-hat stage really seems to be right and very much what I was looking for. – Ray Toal Nov 9 '16 at 19:58
  • @RayToal - I actually lean toward the approach of fully testing the merge operation before doing the sort (as well as separate testing of the partition operation). I think that the claimed benefits emergent design comes from slowly working toward a known goal. In the case of mergesort, I don't think the goal is sorting in general (because then you'll end up with bubble sort). You know the basic operations, so you work toward those operations; the sort is mostly an afterthought. – kdgregory Nov 9 '16 at 20:33
  • 1
    There's a forth option. Pass the merge function into mergesort and mock its behavior. Then go back and implement merge test first. Delegates are awesome™. – RubberDuck Nov 9 '16 at 21:08
  • @RubberDuck Mocking a integral part of the core domain could lead to some troubles, more specifically when you run the program and the mocked and merge function differ in the least detail. An approach like that should be left for instances where you're working with external resources like from where the list to sort comes from. – cllamach Nov 15 '16 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.