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))))))
halve
once and bind it to a local usinglet
. Functional programming does not mean you need to copy each expression. \$\endgroup\$let
? \$\endgroup\$