Inspired by my merge sort in Scheme, I thought I'd try my hand at implementing other sorting algorithms, starting with simple ones (like insertion sort) and working my way up. So, here we go:(define (insertion-sort lst (lt? <))  (fold-right (lambda (item sorted)                (let-values (((lhs rhs) (span! (cut lt? <> item) sorted)))                  (append! lhs (cons item rhs))))              '() lst))Tested with Racket and Guile; requires SRFIs 1, 11, and 26. (If you want to use this for Guile, you will need to adjust the syntax used for optional arguments.)What I'm looking forI'd like to get critique on my code for better style (from the perspective of a seasoned Schemer) and performance, with the understanding that:Insertion sort is O(n) worst case, and there are obviously more scalable sorting algorithms around.I'm trying to make this a pure-functional implementation, so that you can pass in a literal list datum without invoking undefined behaviour.All the nodes in the sorted list are ultimately created using cons, so I can safely use span! and append! on sorted nodes without undefined behaviour.Things I've consideredI originally implemented this using a left-fold instead of a right-fold. However, SRFI 1 explains that it's usually better to use right-folding when the left-folding version requires reversing afterwards due to better cache locality.A left-folding implementation requires building the sorted list in reverse order in order to maintain the fast if mostly sorted property.Update: coredump asked if the output list could share cons cells with the input list where possible. Here's one possible implementation; the code is somewhat more longwinded than the original implementation, so any suggestions for improvement are welcome here too:(define (insertion-sort lst (lt? <))  (pair-fold-right (lambda (pair sorted)                     (define item (car pair))                     (if (and (eq? (cdr pair) sorted)                              (or (null? sorted)                                  (not (lt? (car sorted) item))))                         pair                         (let-values (((lhs rhs) (span (cut lt? <> item) sorted)))                           (append! lhs (cons item rhs)))))                   '() lst))
Insertion sort in Scheme
sorting;scheme;insertion sort