;mergesort l
;    left, right = split l
;    return merge left, right

;split l return two lists, with half of l's items in one list and half in the other

;merge x, y merges the two already sorted lists into one


(define (mergesort x)
  (cond
   ((null? x) x)
   ((null? (cdr x)) x)
   (else (let* ((pair (split x #f))
                (left (car pair))
                (right (cdr pair)))
           (merge (mergesort left) (mergesort right))))))


; split returns a pair of lists.  It adds (car x) to the left list if which is
; #t and the right list if which is #f.  When it recurses, it negates which so
; that it adds the two lists evenly.
(define (split x which)
  (if (null? x)
      (cons '() '())
      (let* ((pair (split (cdr x) (not which)))
             (left (car pair))
             (right (cdr pair)))
        (if which
            (cons (cons (car x) left) right)
            (cons left (cons (car x) right))))))

(define (merge left right)
  (cond
   ((null? left) right)
   ((null? right) left)
   ((< (car left) (car right)) (cons (car left) (merge (cdr left) right)))
   (else                       (cons (car right) (merge left (cdr right))))))