Return to Revisions

Four years, 1400 views, and two dozen upvotes before a review on a site dedicated to code reviews points toward unreviewability as a prominent feature of the code. What hinders reviewability is, I think, the high level of cognitive load the code places on anyone reading it.

##Reading

1. The cognitive load begins at the top level. Merge-sort is a well documented algorithm. Like many people interested in programming, I wrote an implementation for an algorithms class. It makes a good assignment because the details are non-trivial (and discovering those details was serious work seventy years ago when the John Von-Neumann for which computings Von-Neumann Architecture is named, did so...how serious? one might ask and the answer would be Manhattan Project serious). I imagine I'm like some other people in that I've forgotten the ins and outs of my implementation and recycled whatever synapses were storing the pseudo-code to something else. For me, merge-sort is vaguely familiar in a sort of \$\mathcal{O}(n\log n)\$ sort of way since that's the fact that's most likely to be relevant at the sorting level of abstraction.

2. For the purposes of this review, I'll say that the next level down is the top level of the implementation. Here the question claims a clever implementation detail: calculating the length of the list only once. I don't recall how my implementation calculated length or whether it did...I think I used vectors/arrays rather than lists [I wrote it in either Clojure or Racket]. Anyway, being clever makes the code harder to review.

3. At the next level down, the structure induces additional cognitive load. At best the mixture of define and let/let* is inconsistent style. At worst, the let's just make for less readable code of the sort that made nested define's worth implementing in Scheme itself.

4. Finally, there's variable names.

##Advice

1. Help the reader by commenting the code. Don't require expertise in merge-sort as a pre-requisite to understanding. Consider using something like the HtDP Program Recipe as a starting point. Explain the algorithm and use the terms of that explanation in the implementation.

2. I'm reminded of Kernighan's Lever: Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it? Looking at the code, it isn't obvious where the innovation is implemented. Even after I obtain some level of merge-sort knowledge, I still have detective work to understand the innovation. Make the innovation explicit.

3. Make everything explicit using define rather than let/let* the syntax is better and the high level concepts can be articulated together rather than mixed in among the implementation details, e.g. merge can be defined alongside truthy=?, mid, etc.

4. There's no need to name parameters/variables using the criteria for minified JavaScript. l and r might be abstractions 'left' and 'right' but left and right are not abstractions that are explicit in the code. It's only via research that a reader might possibly make the connection.

A bit more on Item 2: If performance is a concern the question of why lists and parameter passing rather than vectors or some other data structure seems relevant. Going further, benchmarking is probably the best justification for added complexity:

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

Fast sorting seems to be a place where using an FFI is the road to meaningful improvement for interestingly sized data.