Skip to content

Instantly share code, notes, and snippets.

@acj
Created October 3, 2011 16:43
Show Gist options
  • Save acj/1259558 to your computer and use it in GitHub Desktop.
Save acj/1259558 to your computer and use it in GitHub Desktop.
Merge sort in Clojure
; Example usage: (mergesort [5 1 8 16 25 11 4])
(ns mergesort
(:use clojure.contrib.math))
(defn merge-two
"Merge two (already sorted) vectors"
[vec1 vec2]
(let [v1f (first vec1) v2f (first vec2)]
(cond
(empty? vec1) vec2
(empty? vec2) vec1
(< v1f v2f)
(cons v1f (merge-two (rest vec1) vec2))
:else
(cons v2f (merge-two (rest vec2) vec1)))))
(defn mergesort
"Sort a vector of numbers using the merge sort algorithm"
[vec]
(let [vecsize (count vec) seam (ceil (/ vecsize 2))]
(cond
(= vecsize 1) (vector (get vec 0))
(= vecsize 2)
(do
(if (< (get vec 0) (get vec 1))
(vector (get vec 0) (get vec 1))
(vector (get vec 1) (get vec 0))))
:else
(merge-two
(mergesort (subvec vec 0 seam))
(mergesort (subvec vec seam))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment