Skip to content

Instantly share code, notes, and snippets.

@rxacevedo
Last active August 29, 2015 14:01
Show Gist options
  • Save rxacevedo/e0091b0fdb83c554486d to your computer and use it in GitHub Desktop.
Save rxacevedo/e0091b0fdb83c554486d to your computer and use it in GitHub Desktop.
Merge sort in Clojure (probably not optimal)
;; Quicky Merge sort and test
(defn merge-sort [coll]
(letfn [(sort [coll]
(if (= 1 (count coll)) coll
(let [sz (count coll)
left (take (/ sz 2) coll)
right (drop (/ sz 2) coll)]
(merge (sort left) (sort right)))))
(merge [left right]
(loop [acc []
l left
r right]
(cond (and (seq l) (not (seq r))) (recur (conj acc (first l)) (rest l) r)
(and (seq r) (not (seq l))) (recur (conj acc (first r)) l (rest r))
(and (seq l) (seq r)) (if (> (compare (first l) (first r)) 0)
(recur (conj acc (first r)) l (rest r))
(recur (conj acc (first l)) (rest l) r))
:else acc)))]
(sort coll)))
;; => #'user/merge-sort
(require '(cemerick (pomegranate :refer :all)))
;; => nil
(add-classpath "/Users/Roberto/Code/yggdrasil/algorithms_1/lib/stdlib.jar")
;; => nil
(import In)
;; => In
;; Sorted
(let [sorted-coll (->> (In. "/Users/Roberto/Code/yggdrasil/algorithms_1/resources/8Kints.txt")
(.readAllInts)
(merge-sort))]
(apply < sorted-coll))
;; => true
;; Works with duplicates
(let [ints (->> (In. "/Users/Roberto/Code/yggdrasil/algorithms_1/resources/8Kints.txt")
(.readAllInts))
doubled (concat ints ints)
sorted-coll (merge-sort doubled)]
(apply <= sorted-coll))
;; => true
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment