mergesort.clj

(defn merge-seqs
  "Merges two sorted sequences into a single sorted sequence"
  ([left right]
    (merge-seqs (list left right)))
  ([[left right]]
    (loop [l left, r right, result []]
      (let [lhead (first l), rhead (first r)]
        (cond
          (nil? lhead)     (concat result r)
          (nil? rhead)     (concat result l)
          (<= lhead rhead) (recur (rest l) r (conj result lhead))
          true             (recur l (rest r) (conj result rhead)))))))

(defn mergesort
  "Produces a sorted sequence from an input sequence.
  Works best with vectors (since it uses 'count' internally)."
  [xs]
  ((fn mergesort-counted [xs n]
     (if (<= n 1)
       xs
       (let [middle (bit-shift-right n 1)]  ; fast division by 2
         (merge-seqs (map mergesort-counted 
                          (split-at middle xs)        ; two halves
                          [middle (- n middle)])))))  ; count of each half
   xs (count xs)))