(load "utils.ss")


; merge two sorted lists l1 and l2 using the predicate compar.

(define merge
  (lambda (l1 l2 compar)
    (let mergeaux ((l1 l1) (l2 l2) (theres '()))
      (cond ((null? l1) (append (reverse theres) l2))
            ((null? l2) (append (reverse theres) l1))
            (else 
             (let ((c1 (car l1))
                   (c2 (car l2)))
               (if (not (compar c2 c1)) ;to make it stable
                   (mergeaux (cdr l1) l2 (cons c1 theres))
                   (mergeaux l1 (cdr l2) (cons c2 theres)))))))))

; breaks up the list into the odd-numbered and the even-numbered elements.

(define evenodd
  (lambda (l)
    (let eoaux ((ll l) (elist '()) (olist '()))
      (if (null? ll) (list elist olist)
          (eoaux (cdr ll) olist (cons (car ll) elist))))))

; mergesort using the evenodd breakup.

(define mergesort
  (lambda (l compar divider)
    (cond ((null? l) l)
          ((null? (cdr l)) l)
          (else (let* ((eo (divider l))
                       (elist (car eo))
                       (olist (cadr eo))
                       (esorted (mergesort elist compar divider))
                       (osorted (mergesort olist compar divider)))
                  (merge esorted osorted compar))))))

; subdivides a list l into elements up to the breaker-th element and the rest.

(define subdiv
  (lambda (l breaker)
    (let subdivider ((thelist l) (accum '()) (remaining breaker))
      (if (= remaining 0) (list (reverse accum) thelist)
          (subdivider (cdr thelist) (cons (car thelist) accum) (- remaining 1))))))

; breaks the list l as evenly as possible into two equal halves.
(define halfandhalf
  (lambda (l)
    (if (null? l) (list l l)
        (let* ((thelen (length l))
               (halflen (floor (/ thelen 2))))
          (subdiv l halflen)))))
   
; stable mergestort
(define mergesortstable
  (lambda (l compar)
    (mergesort l compar halfandhalf)))