# Mergesort implementation in Clojure

(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)


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).

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"