; from rosettacode.org

function insertionSort(array A)        ; imperative pseudocode
    for i from 1 to length[A]-1 do
        value := A[i] 
        j := i-1
        while j >= 0 and A[j] > value do
            A[j+1] := A[j]
            j := j-1
        done
        A[j+1] = value
    done

(defn in-sort [data]                    ; Clojure code
  (letfn [(insert ([raw x](prn "** " raw)(insert [] raw x))
		  ([sorted [y & raw] x]
                (prn sorted y raw x)         
		     (if (nil? y) 
                    (conj sorted x)               ; add to end
		         (if (<= x y )  
                       (concat sorted [x,y] raw)   ; fits here
			       (recur (conj sorted y) raw x)) ) ) )] ; 
move rt.	
    (reduce insert [] data)))                     ; insert each value

user=> (in-sort [6,8,5,9,3,2,1,4,7])
"** " []
[] nil nil 6
"** " [6]
[] 6 nil 8
[6] nil nil 8
"** " [6 8]
[] 6 (8) 5
"** " (5 6 8)
[] 5 (6 8) 9
[5] 6 (8) 9
[5 6] 8 nil 9
[5 6 8] nil nil 9
"** " [5 6 8 9]
[] 5 (6 8 9) 3
"** " (3 5 6 8 9)
[] 3 (5 6 8 9) 2
"** " (2 3 5 6 8 9)
[] 2 (3 5 6 8 9) 1
"** " (1 2 3 5 6 8 9)
[] 1 (2 3 5 6 8 9) 4
[1] 2 (3 5 6 8 9) 4
[1 2] 3 (5 6 8 9) 4
[1 2 3] 5 (6 8 9) 4
"** " (1 2 3 4 5 6 8 9)
[] 1 (2 3 4 5 6 8 9) 7
[1] 2 (3 4 5 6 8 9) 7
[1 2] 3 (4 5 6 8 9) 7
[1 2 3] 4 (5 6 8 9) 7
[1 2 3 4] 5 (6 8 9) 7
[1 2 3 4 5] 6 (8 9) 7
[1 2 3 4 5 6] 8 (9) 7
(1 2 3 4 5 6 7 8 9)