# Functional Merge Sort

I just finished this Merge Sort in Clojure, structured according to ex. 22-26 of this workshop.

The main question I have can be answered without spending time understanding the code: halve is called twice in merge-sort, is this still $\mathcal{O}(n \log n)$? (last lines in the code sample) Since it's functional programming, I can't think of a way to avoid calculating halve twice (can't stash the result into a variable).

I followed the structure set out in the exercises, but I think this code is bloated and hard to read. How would you improve the individual functions while maintaining the general structure?

(defn my-take-r [a-list n coll]
(if (or
(= 1 n)
(singleton? coll))
(concat
a-list
(list (first coll)))
(recur
(concat a-list (list (first coll)))
(dec n)
(rest coll))))

(defn my-take [n coll]
(if (empty? coll)
()
(my-take-r () n coll)))

(defn my-drop [n coll]
(if (or (zero? n) (empty? coll))
(concat () coll)
(my-drop (dec n) (rest coll))))

(defn halve [a-seq]
(let [i (int (/(count a-seq) 2))]
(vec (list
(concat () (seq (subvec (vec a-seq) 0 i)))
(concat () (seq (subvec (vec a-seq) i)))))))

(defn seq-merge-r [output a-seq b-seq]
(cond (and
(empty? a-seq)
(empty? b-seq)) output
(empty? a-seq) (concat output b-seq)
(empty? b-seq) (concat output a-seq)
(<
(first a-seq)
(first b-seq)) (seq-merge-r (conj output (first a-seq)) (rest a-seq) b-seq)
:else            (seq-merge-r (conj output (first b-seq)) a-seq (rest b-seq))))

(defn seq-merge [a-seq b-seq]
(seq-merge-r [] (seq a-seq) (seq b-seq)))

(defn merge-sort [a-seq]
(cond
(empty? a-seq) a-seq
(singleton? a-seq) a-seq
:else (seq-merge
(merge-sort (first  (halve a-seq)))
(merge-sort (second (halve a-seq))))))

• Of course you can stash the result, calculate halve once and bind it to a local using let. Functional programming does not mean you need to copy each expression. – Yuri Steinschreiber Jul 28 '16 at 6:59
• Isn't it executed twice even if I bind the function to some shorthand using let`? – Atte Juvonen Jul 28 '16 at 11:23
• No, you are not binding a function to a shorthand. You are evaluating an expression (which in turn calls a function) and binding the result to a local. Then you are referring to that local which is the same as referring to the value it is bound to. Clojure, like any Lisp, is eagerly evaluated, so binding a local to an expression does not defer its evaluation. But even in real lazy languages like Haskell binding an expression to a local this way will still evaluate the expression only once - these languages usually use "call by need" evaluation strategy. – Yuri Steinschreiber Jul 28 '16 at 15:28