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:
- 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.
- Comments on
merge uses "right-folding" (whereas my
merge uses "left-folding"), which is why it looks so different, but both are legitimate strategies.
- 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.
split zigzags the elements between the two output lists rather than splitting midway, which was what made me doubt the sort stability.
The inner function
splitr could be reformulated using a named
let, which is more idiomatic in Scheme:
(define (split l)
(let loop ((l l)
(if (null? l)
(list left right)
(loop (cdr l) right (cons (car l) left)))))
- 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.
In the outer
- You should merge the first two
cond tests into a single
(or (null? l) (null? (cdr l))) test.
Instead of the sequential
let* binding of
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
(values left right), you could do:
(let-values (((left right) (split l)))
which is much more succinct.
In summary, I'd suggest two fixes:
- You should make the function handle "equal" elements correctly.
- 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))