mergesort.clj

(defn mrg [[x & xrest :as X] [y & yrest :as Y] R]
  (if (and X Y)
    (if (<= x y)
      (recur xrest Y (conj R x))
      (recur X yrest (conj R y)))
    (concat R X Y)))

(defn mrgsrt [X]
  (if (> (count X) 1)
    (let [[left right] (split-at (/ (count X) 2) X)]
      (mrg (mrgsrt left) (mrgsrt right) []))
    X))