Sorting algorithm O(N^2). More info here http://en.wikipedia.org/wiki/Insertion_sort and here https://www.youtube.com/watch?v=8oJS1BMKE64

insertionsort.clj

(defn insertionsort [lns]
  (let
    [insert
     (fn insert [n lns]
       (if (or (empty? lns) (< n (first lns)))
         (cons n lns)
         (cons (first lns)
               (insert n (rest lns)))))]
    (loop [sns '()
           lns lns]
      (if (empty? lns)
        sns
        (recur
         (insert (first lns) sns)
         (rest lns))))))

(insertionsort '(3 4 12 3 45 1 -1 -30))
;;=> (-30 -1 1 3 3 4 12 45)