Another Scheme Mergesort

Question

Here's a merge sort I wrote trying to learn Scheme.

(define mergesort
  (lambda (l cmp)
    (define merge
      (lambda (left right)
        (cond
          ((null? left) right)
          ((null? right) left)
          ((cmp (car left) (car right)) (cons (car left) (merge (cdr left) right)))
          (else (merge right left)))))
    (define split
      (lambda (l)
        (define splitr
          (lambda (l left right)
            (if (null? l)
                (list left right)
                (splitr (cdr l) right (cons (car l) left)))))
        (splitr l '() '())))
    (cond
      ((null? l) l)
      ((null? (cdr l)) l)
      (else (let* ((parts (split l))
                   (left (car parts))
                   (right (cadr parts)))
              (merge (mergesort left cmp)
                     (mergesort right cmp)))))))

I know there's already a merge sort question on code review. Frankly, that approach has some nuances I'm not sure I'm prepared to understand yet. So here's my much more naïve approach.

So, keeping in mind I'm pretty much still an FP newbie (so if I don't understand your critique, I'll ask followup questions) and I may have missed some opportunities to do things "the scheme way", how did I do?

Answer 1

Code Review questions don't have a concept of duplicates per se. You're looking for people to look at your code, not my code! :-)

In so saying, here are my comments:

1. The most important thing I noted is that your function doesn't seem to maintain sort stability. At least, I don't see any active effort to keep the sorting stable.
2. Comments on merge:
   1. Your merge uses "right-folding" (whereas my merge uses "left-folding"), which is why it looks so different, but both are legitimate strategies.
   2. Your code doesn't correctly handle the case where two elements compare "equal" though (where (cmp a b) and (cmp b a) both return false). In particular, it will loop endlessly.

3. Comments on split:

   1. Your split zigzags the elements between the two output lists rather than splitting midway, which was what made me doubt the sort stability.

   2. The inner function splitr could be reformulated using a named let, which is more idiomatic in Scheme:

      (define (split l)
        (let loop ((l l)
                   (left '())
                   (right '()))
          (if (null? l)
              (list left right)
              (loop (cdr l) right (cons (car l) left)))))
      

   3. Personally, I'd use (values left right) instead of (list left right), to return the sublists as two values. I'll explain why in the final point.

4. In the outer mergesort function:

   1. You should merge the first two cond tests into a single (or (null? l) (null? (cdr l))) test.

   2. Instead of the sequential let* binding of parts then left then right, you should use either this:

      (let ((parts (split l)))
        (let ((left (car parts))
              (right (cadr parts)))
          ...))
      

      or, if you took my suggestion to have split return (values left right), you could do:

      (let-values (((left right) (split l)))
        ...)
      

      which is much more succinct.

In summary, I'd suggest two fixes:

1. You should make the function handle "equal" elements correctly.
2. You should make the function provide stable sorting, namely that if two elements in the input list are "equal" to each other, you should keep their relative order in the output list (see my test case below).

---

You can use this as a test case:

(mergesort '((3 . 1) (1 . 4) (4 . 1) (1 . 5) (5 . 9)
             (9 . 2) (2 . 6) (6 . 5) (5 . 3) (3 . 5))
           (lambda (x y) (< (car x) (car y))))

The correct result should be:

((1 . 4) (1 . 5) (2 . 6) (3 . 1) (3 . 5)
 (4 . 1) (5 . 9) (5 . 3) (6 . 5) (9 . 2))