(define split
(lambda (ls)
(letrec ((split-h (lambda (ls ls1 ls2)
(cond
((or (null? ls) (null? (cdr ls)))
(cons (reverse ls2) ls1))
(else (split-h (cddr ls)
(cdr ls1) (cons (car ls1) ls2)))))))
(split-h ls ls '()))))
(define (merge lst1 lst2)
(if (null? lst1)
lst2
(if (null? lst2)
lst1
(if (< (car lst1) (car lst2))
(cons (car lst1) (merge (cdr lst1) lst2))
(cons (car lst2) (merge lst1 (cdr lst2)))))))
(define mergesort
(lambda (pred ls)
(cond
((null? ls) ls)
((null? (cdr ls)) ls)
(else (let ((splits (split ls)))
(merge (mergesort pred (car splits)) (mergesort pred (cdr splits))))))))
(display (mergesort '() '(3 5 1 4 2)))