>>1
This is not a merge sort because you are not breaking the list in half
when you call merge:
merge (list (car l)) (merge-sort (cdr l)))))
Heres a merge sort I wrote where the merging and breaking are tail recursive
(define (merge-sort comparison lis)
(define (break fst snd tail)
(cond
((null? tail ) (cons fst snd))
((null? (cdr tail)) (cons (cons (car tail) fst) snd))
(else (break
(cons (car tail) fst)
(cons (cadr tail) snd)
(cddr tail)))))
(define (mix-rev fst snd acc orientation)
(cond
((and (null? fst) (null? snd)) acc)
((null? fst)
(mix-rev `() (cdr snd) (cons (car snd) acc) orientation))
((null? snd)
(mix-rev (cdr fst) `() (cons (car fst) acc) orientation))
((eq? orientation (comparison (car fst) (car snd)))
(mix-rev (cdr fst) snd (cons (car fst) acc) orientation))
(else
(mix-rev fst (cdr snd) (cons (car snd) acc) orientation))))
(define (oriented-sort lis orientation)
(cond
((null? lis) lis)
((null? (cdr lis)) lis)
((null? (cddr lis))
(if (eq? orientation (comparison (car lis) (cadr lis))) lis
(list (cadr lis) (car lis))))
(else (let ((rec (break `() `() lis)))
(mix-rev
(oriented-sort (car rec) (not orientation))
(oriented-sort (cdr rec) (not orientation))
`() (not orientation) )))))
(oriented-sort lis #t))