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


    (define (sort-len cmp xs len)
      (if (<= len 1)
        xs
        (let ((n/2 (truncate-quotient len 2)))
          (let-values (((half-a half-b) (split-at n/2 xs)))
            (let ((sorted-half-a (sort-len cmp half-a n/2))
                  (sorted-half-b (sort-len cmp half-b (- len n/2))))
              (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))))))))))


    (define (sort cmp xs)
      (sort-len cmp xs (length xs)))))