Merge sort in Scheme

Question

(define (merge-sort lst (lt? <))
  (define (truthy=? a b)
    (eq? (not a) (not b)))

  (let sort ((lst lst)
             (size (length lst))
             (flip #f))
    (define (merge l r (res '()))
      (cond ((null? l) (append-reverse r res))
            ((null? r) (append-reverse l res))
            ((truthy=? (lt? (car r) (car l)) flip)
             (merge l (cdr r) (cons (car r) res)))
            (else
             (merge (cdr l) r (cons (car l) res)))))

    (if (<= size 1) lst
        (let*-values (((mid) (quotient size 2))
                      ((l r) (split-at lst mid)))
          (merge (sort l mid (not flip))
                 (sort r (- size mid) (not flip)))))))

Tested with Racket and Guile; requires SRFIs 1 and 11. (If you want to use this for Guile, you will need to adjust the syntax used for optional arguments.)

This version is tailored for Scheme in a number of ways:

• The length of the list is calculated only once, at the beginning. At each split, the length of the split parts is passed to each recursive call.
• The merge step uses a right-unfold rather than a left-unfold, to be tail-recursive. This results in a reversed list at each step.
• Rather than reverse the list at each merge, I just keep a flag saying whether the lists are reversed. The merging step takes this flag into account and then does the right kind of merge to maintain sort stability.

Answer 1

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 computing's 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.