From d1c59f340c623eb533f1b59564b0e3cd8f5ca728 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sat, 22 Jan 2022 17:51:32 -0800 Subject: Store the list length in sort. Computing length each time is very unnecessary. --- csc/sort.csc | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) diff --git a/csc/sort.csc b/csc/sort.csc index 62b1c9d..6be1e16 100644 --- a/csc/sort.csc +++ b/csc/sort.csc @@ -7,13 +7,13 @@ (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))) + (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 '())) @@ -21,4 +21,8 @@ ((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)))))))))))) + (else (loop (cdr a) b (cons (car a) acc)))))))))) + + + (define (sort cmp xs) + (sort-len cmp xs (length xs))))) -- cgit v1.3.1