Merge sort in Clojure

Question

I made my own version of merge sort:

 (defn rsort[a]
 (cond 
 (<= (count a) 1) a
 :else 
 (let [half (/ (count a) 2) 
 [lh rh] (split-at half a)]
 (loop [res () slh (rsort lh) srh (rsort rh)]
 (cond 
 (empty? slh) (into srh res)
 (empty? srh) (into slh res)
 :else 
 (if (< (first slh) (first srh))
 (recur (cons (first slh) res) (rest slh) srh)
 (recur (cons (first srh) res) slh (rest srh))))))))

Any suggestion how improve this code?

• MattPutnam: Does this work with lists? Your usage if into makes me think it will only work with vectors.
• Roman Makhlin: Yeah, Its works for list and vectors as well.
• Heslacher: Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers .

Answer 1

I tested with a couple of input values and for the most part, it seem fine. Note however, that the standard sort also works with e.g. [1 nil] (with output [nil 1]) whereas this code breaks with an exception during the comparison.

Code looks fine with a few minor issues:

• The name should be merge-sort; rsort is not meaningful.
• The values (first slh) and (first srh) are written down twice; the compiler might optimise that away, but IMO it would be nicer to have a separate let for them.
• Emacs' clojure-mode indents the :else branch differently, dunno about that.

Some suggestions:

• Support the same signature as the standard sort.
• Add a docstring explaining the function.
• Add tests, possibly with randomised input as well.