scheme-merge-sort

(define (split-in-half lst)
  (let ((left-length (div (length lst) 2)))
    (values (take lst left-length)
            (drop lst left-length))))

(define (split-by-less-or-equal n lst)
  (define (do-split lst true-acc false-acc)
    (if (null? lst)
        (values true-acc false-acc)
        (let ((next (car lst))
              (rest (cdr lst)))
          (if (<= next n)
              (do-split rest (append true-acc (list next)) false-acc)
              (do-split rest true-acc (append false-acc (list next)))))))

  (do-split lst '() '()))

(define (merge left right)
  (define (do-merge left right acc)
    (if (null? left)
        (append acc right)
        (let ((next (car left)))
          (let-values (((less-or-equal greater)
                        (split-by-less-or-equal next right)))
            (do-merge (cdr left)
                      greater
                      (append acc less-or-equal (list next)))))))

  (if (or (null? left)
          (null? right))
      (append left right)
      (do-merge left right '())))

(define (merge-sort list)
  (let-values (((left right) (split-in-half list)))
    (if (and (< (length left) 2)
             (< (length right) 2))
        (merge left right)
        (merge (merge-sort left) (merge-sort right)))))