Insertion sort in Scheme 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? &lt;))
  (fold-right (lambda (item sorted)
                (let-values (((lhs rhs) (span! (cut lt? &lt;&gt; 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 for

I'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 considered


I 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? &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? &lt;&gt; item) sorted)))
                           (append! lhs (cons item rhs)))))
                   '() lst))
I am not a seasoned Schemer and I think your code looks great as-is. I have only one remark. 

You are sorting the list in a purely functional way in order to avoid mutating the list given in input. But I am not sure about what is your intent w.r.t. data-sharing, which is one of the strong point of purely functional data-structures (and maybe you don't want to share cons-cells, which I can understand too).

Currently, it appears to me that you can't have any sublist shared. You do    have an opportunity to share sublists between your intermediate lists, thanks to span! and append!. But if your input list is (6 5 7 8 9) and the sort &lt;, the resulting list (5 6 7 8 9) has no way to share the same  sublist, namely (7 8 9), because you build the result from a fresh list () using cons (apologies for any misunderstanding).

A possible improvement for your implementation is to start finding the longest sublist being already sorted and build the resulting list on top of this sublist. I don't consider this to be in contradiction with the definition of insertion sort. The downside is that mutations are shared too, but this is a design decision (and this is where I failed to see if you are avoiding sharing data on purpose or not).