Taylor Venable committed 6131f5d

Add insertion sort implementation

Comments (0)

Files changed (1)

           (vector-shrink! (bintree-data h) (##fx- (bintree-size h) 1))
           (heapify! h)
           (loop (##fx- i 1) (cons top result)))))))
+(define (insertion-sort lst le)
+  (if (null? lst)
+    (list)
+    (let loop ((items lst)
+               (result '()))
+      (if (null? items)
+        result
+        (if (or (null? result)
+                (le (car items) (car result)))
+          ;; result list is empty, or for sorting reasons
+          ;; item goes into the head of the list
+          (loop (cdr items) (cons (car items) result))
+          (let loop2 ((searching result))
+            (if (or (null? (cdr searching))
+                    (le (car items) (car (cdr searching))))
+              ;; item goes at the end of the result
+              ;; or between the car and cdr of the result
+              (begin
+                (set-cdr! searching (cons (car items) (cdr searching)))
+                (loop (cdr items) result))
+              (loop2 (cdr searching)))))))))