(defn insertion-sort [ks]
  (reduce (fn [a x]
            (let [[h t] (split-with #(< % x) a)]
              (concat h [x] t)))
    [] ks))

(defn merge-sort [ks]
  (let [c (count ks)]
    (if (= c 1) ks
      ((fn m [[[ah & ar :as a] [bh & br :as b]]]
         (cond (nil? ah) b
               (nil? bh) a
               (< ah bh) (cons ah (m [ar b]))
               :else     (cons bh (m [a br]))))
       (map merge-sort (split-at (quot c 2) ks))))))

(defn quick-sort [[k & ks]]
  (if (nil? k) []
    (apply #(concat %1 [k] %2)
      (map quick-sort
        (reduce (fn [[a b] x]
                  (if (< k x) [a (conj b x)] [(conj a x) b]))
                [[] []] ks)))))