Insertion Sort

insertion-sort.clj

(defn insert [val lst]
  (cond
    (empty? lst) (list val)            ; if it's an empty list, initialize it
    (> (first lst) val) (conj lst val) ; if the first item is smaller than the first of lst, just conj
    :else 
    (conj (insert val (rest lst)) (first lst)))) ; otherwise we need to keep calling insert recursively

(defn insertion-sort [lst]
  (loop [list lst result '()]  ; create local variables for our result set and the list passed in
    (if (empty? list) result   ; if the list passed in was empty, just return our empty result list
      (recur (rest list) (insert (first list) result))))) ; otherwise, recursively insert into the result list