1 files changed, 24 insertions, 0 deletions
diff --git a/sort.csc b/sort.csc
new file mode 100644
index 0000000..62b1c9d
--- /dev/null
+++ b/sort.csc
@@ -0,0 +1,24 @@
+(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))))))))))))