merge-sort.clj

(defn merge-step
  "Merges two sorted collections into one sorted sequence
   using comparator"
  [cmp left-coll right-coll]
  (loop [[lh & lt :as lc] left-coll
         [rh & rt :as rc] right-coll
         out []]
    (cond
      (empty? lc) (concat out rc)
      (empty? rc) (concat out lc)
      (cmp lh rh) (recur lt rc (conj out lh))
      :else (recur lc rt (conj out rh)))))

(defn merge-sort-recursive
  "Sorts collection using comparator (recursive implementation)"
  [cmp coll]
  (let [n (count coll)]
    (if (< n 2)
        coll
        (->>  coll
              (split-at (bit-shift-right n 1))
              (map (partial merge-sort-recursive cmp))
              (apply merge-step cmp)))))

(defn merge-sort
  "Sorts collection using comparator"
  [cmp coll]
  (loop [[h & t :as in] (map list coll)]
    (if (empty? t)
        h
        (recur (map (fn [[l r]] (merge-step cmp l r))
                    (partition-all 2 in))))))