Lazy sorting implementations in Clojure

lazy_sort.clj

(ns lazy-sort)

(defn qsort [[head & tail]]
  (when head
    (lazy-cat (qsort (filter #(< % head) tail))
              [head]
              (qsort (remove #(< % head) tail)))))

(defn merge*
  [[f1 & r1 :as l1] [f2 & r2 :as l2]]
  (cond
    (nil? f1) l2
    (nil? f2) l1
    (<= f1 f2) (lazy-seq (cons f1 (merge* r1 l2)))
    (> f1 f2) (lazy-seq (cons f2 (merge* l1 r2)))))

(defn msort [s]
  (if (next s)
    (let [[left right] (split-at (/ (count s) 2) s)]
      (merge* (msort left) (msort right)))
    s))

(defn hsort [s]
  (let [heap (java.util.concurrent.PriorityBlockingQueue. s)]
    (repeatedly (count s) #(.take heap))))

(defn insert [^java.util.LinkedList s x]
  (let [i (.listIterator s (.size s))]
    (while (and (.hasPrevious i) (> (.previous i) x)))
    (.add i x)
    s))

(defn isort [s] ; not lazy
  (seq (reduce insert (java.util.LinkedList.) s)))

(defn treeduce [f s]
  (loop [s (partition-all 2 s)]
    (let [s (map (fn [[x y]] (f x y)) s)]
      (if (< 1 (count s))
        (recur (partition-all 2 s))
        (first s)))))

(defn tsort [s] ; naive
  (treeduce merge* (map isort (partition-all 128 s))))

(defn speed []
  (doseq [s [#'sort #'qsort #'msort #'hsort #'isort #'tsort]
          :let [sort (var-get s)]]
    (println)
    (print "all   " s "")
    (time (dotimes [_ 100] (dorun (sort (shuffle (range 1000))))))
    (print "sorted" s "")
    (time (dotimes [_ 100] (dorun (sort (range 1000)))))
    (print "first " s "")
    (time (dotimes [_ 100] (first (sort (shuffle (range 1000))))))))

test.clj

all    #'clojure.core/sort "Elapsed time: 67.987 msecs"
sorted #'clojure.core/sort "Elapsed time: 22.214 msecs"
first  #'clojure.core/sort "Elapsed time: 56.249 msecs"

all    #'test/qsort "Elapsed time: 717.93 msecs"
sorted #'test/qsort "Elapsed time: 12388.316 msecs"
first  #'test/qsort "Elapsed time: 30.976 msecs"

all    #'test/msort "Elapsed time: 1317.334 msecs"
sorted #'test/msort "Elapsed time: 945.077 msecs"
first  #'test/msort "Elapsed time: 708.803 msecs"

all    #'test/hsort "Elapsed time: 83.909 msecs"
sorted #'test/hsort "Elapsed time: 75.235 msecs"
first  #'test/hsort "Elapsed time: 28.91 msecs"

all    #'test/isort "Elapsed time: 140.147 msecs"
sorted #'test/isort "Elapsed time: 23.097 msecs"
first  #'test/isort "Elapsed time: 110.453 msecs"

all    #'test/tsort "Elapsed time: 310.026 msecs"
sorted #'test/tsort "Elapsed time: 187.124 msecs"
first  #'test/tsort "Elapsed time: 72.164 msecs"