From 3ff7aac2d2eb2cbf2f854793fc0d7bc6f1f7d927 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sun, 9 Jan 2022 08:40:09 -0800 Subject: Initial commit. Not sure if everything here will be needed eventually, but we have a working bytecode interpreter. Next I will write the linker, then the core compiler, and finish with the macro expander. --- sort.csc | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 sort.csc (limited to 'sort.csc') 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)))))))))))) -- cgit v1.3.1