gistfile1.scm

(define (split-list lyst n)
  (let ((result (make-vector 3)))
    (vector-set! result 0 lyst)
    (let loop ((i n))
      (unless (null? lyst)
              (if (= i 1)
                  (let ((tmp lyst))
                    (set! lyst (cdr lyst))
                    (set-cdr! tmp ()))
                  (begin
                    (set! lyst (cdr lyst))
                    (loop (- i 1))))))
    (vector-set! result 1 lyst)
    (let loop ((i n))
      (unless (null? lyst)
              (if (= i 1)
                  (let ((tmp lyst))
                    (set! lyst (cdr lyst))
                    (set-cdr! tmp ()))
                  (begin
                    (set! lyst (cdr lyst))
                    (loop (- i 1))))))
    (vector-set! result 2 lyst)
    result))                  
              

(define (merge l1 l2)
    (let loop ((p l1) (q l2) (result ()))
      (cond ((null? p) (append result q))
            ((null? q) (append result p))
            (else 
             (if (> (car p) (car q))
                 (loop p (cdr q) (append result (list (car q))))
                 (loop (cdr p) q (append result (list (car p)))))))))

(define (merge-sort lyst)
  (let outer-loop ((k 1) (l lyst))
    (let inner-loop ((l l) (result ()))
      (letrec ((v (split-list l k))
               (merged (merge (vector-ref v 0)
                              (vector-ref v 1)))
               (rest (vector-ref v 2))
               (new (append result merged)))
        
        (if (null? rest)
            (if (null? result)
                merged
                (outer-loop (* k 2) new))
            (inner-loop rest new))))))