Edd Mann Developer

Mergesort in Clojure using Post Conditionals

Whilst currently reading through The Joy of Clojure book I was introduced to the concept of pre and post-conditionals, similar to another language I have heard about called Eiffel. To experiment with this feature I decided to create a simple merge-sort algorithm implementation which provided the post invariant that its returned values were sorted by the provided predicate.

(defn sorted? [pred? col]
  (every? #(apply pred? %) (partition 2 1 col)))

(defn merge
  ([pred? left right]
   {:post [(sorted? pred? %)]}
   (loop [[l & lr :as ls] left [r & rr :as rs] right acc []]
     (if (and l r)
       (if (pred? l r)
         (recur lr rs (conj acc l))
         (recur ls rr (conj acc r)))
       (concat acc ls rs)))))

(defn half [col]
  (split-at (/ (count col) 2) col))

(defn merge-sort
  ([col] (merge-sort < col))
  ([pred? col]
    {:post [(sorted? pred? %)]}
    (if (< (count col) 2)
      (let [[left right] (half col)]
        (merge pred? (merge-sort pred? left) (merge-sort pred? right))))))

I really liked the manner in which I could use the ‘partition’ function to succinctly map the task of splitting on each co-located pair of values within a collection in code. We are able to then put this implementation into practice by optionally providing a predicate (else defaulting to ascending order).

(def numbers (shuffle (range 1 11))) ; [1 9 7 2 10 3 6 5 4 8]

(merge-sort numbers) ; (1 2 3 4 5 6 7 8 9 10)
(merge-sort > numbers) ; (10 9 8 7 6 5 4 3 2 1)