Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(defn mrg [[x & xrest :as X] [y & yrest :as Y] R]
(if (and (not-empty X) (not-empty Y))
(if (<= x y)
(mrg xrest Y (conj R x))
(mrg X yrest (conj R y)))
(concat R X Y)))
(defn mrgsrt [X]
(if (> (count X) 1)
(let [sides (split-at (/ (count X) 2) X)]
(mrg (mrgsrt (get sides 0)) (mrgsrt (get sides 1)) []))
X))
@kdubovikov

This comment has been minimized.

Copy link

kdubovikov commented May 2, 2014

Wow, a great implementation!

@l1x

This comment has been minimized.

Copy link

l1x commented May 5, 2014

Not bad, but :

=> (time (mrgsrt (shuffle (range 100000))))

StackOverflowError   clojure.lang.RT.nthFrom (RT.java:852)
@divs1210

This comment has been minimized.

Copy link

divs1210 commented Sep 9, 2014

Great implementation!
The mrg function can be TCO'd by replacing self-calls with recur, though.
Prevents stack-overflow and boosts performance.

(time (merge-sort (shuffle (range 100000))))
;=> "Elapsed time: 2128.452362 msecs"
@egri-nagy

This comment has been minimized.

Copy link

egri-nagy commented May 11, 2015

With recur, in a single function: https://gist.github.com/egri-nagy/512998bd8482fc49947b

@umiki7

This comment has been minimized.

Copy link

umiki7 commented Oct 2, 2016

Also, the merge function can be implemented as a lazy sequence:

(defn mrg
  [p q]
  (let [pf (first p)
        ps (rest p)
        qf (first q)
        qs (rest q)]
    (lazy-seq
      (cond
        (not qf)  p
        (not pf)  q
        (< pf qf) (cons pf (mrg ps q))
        :else     (cons qf (mrg p  qs))))))

Interestingly destructuring negatively impacts performance.

@WarFox

This comment has been minimized.

Copy link

WarFox commented Oct 14, 2019

Nice one!

I made it a bit more readable

(defn merge
  [[l & *left :as left] [r & *right :as right] acc]
  (if (and (not-empty left) (not-empty right))
    (if (<= l r)
      (recur *left right (conj acc l))
      (recur left *right (conj acc r)))
    (concat acc left right)))

(defn merge-sort [list]
  (if (> (count list) 1)
    (let [[left right] (split-at (/ (count list) 2) list)]
      (merge (mergesort left) (mergesort right) []))
    list))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.