merge-sort.clj

(defn half
  [s]
  (bit-shift-right (count s) 1))  ;; faster division by 2

(defn left-right
  [v]
  (let [v (if-not (vector? v) (vec v) v)
        h (half v)]
    [(subvec v 0 h) (subvec v h)]))

(defn single-element?
  [s]
  (= (count s) 1))

(defn merge-lr
  [left right]
  (let [left-head  (first left)
        right-head (first right)]
    (cond
      (nil? left-head)  right
      (nil? right-head) left
      :else (if (< left-head right-head)
              (cons left-head (lazy-seq
                                (merge-lr (rest left) right)))
              (cons right-head (lazy-seq
                                 (merge-lr left (rest right))))))))

(defn merge-sort
  [s]
  (if (single-element? s)
    s
    (let [[left right] (left-right s)]
      (merge-lr (merge-sort left)
                (merge-sort right)))))