Mergesort implementation in Clojure

Question

(defn merge [pred left right]
    (loop [v [] l left r right]   ; v is a vector, so conj will append to the end
        (if (and (seq l) (seq r)) ; if both left and right are not empty
            (if (pred (first l) (first r))
                (recur (conj v (first l)) (rest l) r)
                (recur (conj v (first r)) l        (rest r)))
            (concat v l r))))     ; One of l and r is empty, so concatenate what is already sorted

(defn mergesort [pred v]
    (let [
        n (count v) 
        h1 (int (/ n 2))        ; floor(n/2)
        h2 (int (/ (inc n) 2))] ; ceil(n/2)
        (if (< n 2)
            v
            (merge pred
                (mergesort pred (take h1 v))          ; take the first half of elements
                (mergesort pred (take-last h2 v)))))) ; take the last half of elements

I'd like critics on how to turn this mergesort algorithm more Clojuric, if there are any Clojure API I could use to simplify it and other issues.

Specially, I've used a vector to store elements within merge, because otherwise the conj would append to its front, thus producing a reversed sequence. Also, is take and take-last the way to go to catch two halfs of a seq?

The following test code shows it works for vectors, lists and maps. Anything else I should consider?

(def v [3 -2 4 5 -3 0 7 -8 1 -1 2])
(def m [{:x 1 :y 2} {:x 0 :y 3} {:x 2 :y 1}])
(def s (seq v))
(mergesort < v)
;=> (-8 -3 -2 -1 0 1 2 3 4 5 7)
(mergesort > v)
;=> (7 5 4 3 2 1 0 -1 -2 -3 -8)
(mergesort #(< (java.lang.Math/abs %1) (java.lang.Math/abs %2)) v)
;=> (0 -1 1 2 -2 -3 3 4 5 7 -8)
(mergesort #(< (:x %1) (:x %2)) m)
;=> ({:x 0, :y 3} {:x 1, :y 2} {:x 2, :y 1})
(mergesort > s)
;=> (7 5 4 3 2 1 0 -1 -2 -3 -8)

Answer 1

A few points, though I'm not a Clojure expert:

• Indentation. You use four-space indentation, but two-space indentation is more common for Lisp in general and also generally preferred for Clojure. (there seems to be a Clojure community style guide)

• Instead of take-last, you may want to use drop. Since you're traversing the whole list anyway, you could also just use split-at (though that's basically the same as using both take and drop).

Answer 2

I've followed the suggestions in Asumu Takikawa's answer (specially concerning code style) and rewrote the code for future reference. It suffers from an efficiency problem that I still haven't addressed: split-at calls drop, that in turn runs linearly thru the sequence. This is necessary in case of a list, but not with a vector.

(defn merge* [pred left right]
  (loop [v [] l left r right]
    (if (and (seq l) (seq r))
      (if (pred (first l) (first r))
        (recur (conj v (first l)) (rest l) r)
        (recur (conj v (first r)) l        (rest r)))
      (concat v l r))))

(defn mergesort [pred coll]
  (let [n (count coll)]
    (if (< n 2)
      coll
      (let [[left right] (split-at (/ n 2) coll)]
        (merge* pred
                (mergesort pred left)
                (mergesort pred right))))))

I also expected some difference in running times for collections with and without a power-of-two count, but it seems excessive...

(def test-list #(take % (repeatedly rand)))
(def test-mergesort #(time (do (mergesort < (test-list %)) nil)))
(test-mergesort (* 128 1024))
;=> "Elapsed time: 986.060739 msecs"
(test-mergesort (* 127 1031)) ; prime numbers
;=> "Elapsed time: 1344.07105 msecs"