Merge sort in Scheme

(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.