Here, for reference, is another version which turns the tail recursion modulo cons into tail recursion with an accumulator. For the sake of variety, here is also one way to partially simulate the absent type-classes.
(defprotocol Monoid
(mempty [_] )
(mappend [_ xs ys]))
(defn fold-map
[monoid f xs]
(reduce (partial mappend monoid) (mempty monoid) (map f xs)))
(defn- ord-mappend*
[[x & rx :as xs] [y & ry :as ys] a]
(cond
(empty? xs) (concat a ys)
(empty? ys) (concat a xs)
:else (if (< x y)
(recur rx ys (conj a x))
(recur xs ry (conj a y)))))
(def Ord
(reify Monoid
(mempty [_] (list))
(mappend [_ xs ys] (ord-mappend* xs ys []))))
(defn isort [xs] (fold-map Ord list xs))
(defn is-sorted? [xs] (apply < xs))
(is-sorted? (isort (shuffle (range 10000))))
;=> true (sometime later)