(define-library (csc sort)
  (export sort)
  (import (scheme base)
          (only (csc list)
                revappend
                split-at))
  (begin


    (define (sort cmp xs)
      (let ((len (length xs)))
        (if (<= len 1)
            xs
          (let-values (((half-a half-b) (split-at (truncate-quotient len 2) xs)))
            (let ((sorted-half-a (sort cmp half-a))
                  (sorted-half-b (sort cmp half-b)))
              (let loop ((a sorted-half-a)
                         (b sorted-half-b)
                         (acc '()))
                (cond ((null? a) (revappend acc b))
                      ((null? b) (revappend acc a))
                      ((cmp (car b) (car a))
                       (loop a (cdr b) (cons (car b) acc)))
                      (else (loop (cdr a) b (cons (car a) acc))))))))))))