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