;;; mergesort.lsp — functional merge sort
;;; Run: python3 lumbda.py --fast examples/mergesort.lsp

(define (merge a b)
  (cond ((null? a) b)
        ((null? b) a)
        ((< (car a) (car b))
         (cons (car a) (merge (cdr a) b)))
        (else
         (cons (car b) (merge a (cdr b))))))

(define (split lst)
  (let loop ((l lst) (a '()) (b '()))
    (if (null? l)
        (list a b)
        (loop (cdr l) b (cons (car l) a)))))

(define (msort lst)
  (if (or (null? lst) (null? (cdr lst)))
      lst
      (let ((halves (split lst)))
        (merge (msort (car halves))
               (msort (cadr halves))))))

(define data (reverse (iota 20)))
(display "Input:  ") (display data) (newline)
(display "Sorted: ") (display (msort data)) (newline)
