# 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? <))
(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 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:

1. Insertion sort is O(n²) worst case, and there are obviously more scalable sorting algorithms around.
2. 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

1. 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? <))
(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))


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 <, 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).

• Thanks for your feedback! You're right, the current code returns a fresh list every time (similar to my mergesort implementation that I linked to). It's mainly because it keeps the code simple, but, I can see if there's a way to implement the tail-merging in an efficient way. – Chris Jester-Young Sep 28 '15 at 16:32
• I've updated the question to include a shared-tail implementation. Feedback is welcome on that, too. – Chris Jester-Young Sep 28 '15 at 16:58
• @ChrisJester-Young I am looking at your second version but I am not sure I'll have more feedback to give, except that it looks good. – coredump Sep 28 '15 at 20:25

A (very) small point:

The variable name lst is, well, ugly.

I much prefer xs for a list (then you can talk about an element x in the list xs). If you have two lists xs and ys and have elements x and y you know where the elements come from.

Another option is simply 'l'.

A general observation:

Insertion sort are better suited for vectors, where elements can be swapped without allocating any temporary data structures.

It would be interesting to time your list based solution to see if it is O(n^2) or whether the extra allocations make it O(n^3).

• I wrote my function with the mutating versions of span! and append! in mind, where there is no extra allocation. But even in implementations like Racket where all cons cells are immutable (and where span! is span and append! is append), the extra allocations occur in the outermost loop, so the overall algorithm is O(n²), just with a bigger constant. – Chris Jester-Young Oct 21 '15 at 5:25