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

commented May 2, 2014

Wow, a great implementation!

@l1x

This comment has been minimized.

Copy link

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

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

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

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.

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.