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